数组,栈,队列,链表比较

时间:2022-07-01 15:41:31

 

数组

队列

链表

特点

初始容量,定长

先进后出

初始容量,定长

先进先出

初始容量,定长

不定长,动态添加

存储

连续空间

顺序

连续空间

顺序

连续空间

顺序

非连续

非顺序

实现

 

数组

数组,链表

 

结构

下标,数据

栈顶,栈底,出栈,入栈

头(head),尾(tail),出队,入队

(1)元素个数=tail-head

(2)head=tail,队空

(3)head=(tail+1)%length,队满

length数组长度

(4)总有一个位置不放元素

(5)入队时,标记tail后移一位:tail=(tail+1)%length;

两部分:data, next

扩容

将旧的数据复制到新的,更长的数组中

 

拓展

栈实现队列,队列实现栈

数组实现链表