数据结构(堆与队列的线性结构与链式结构)
栈
- 特点
- 先进后出(FILO)
- 线性栈,限定仅在表尾(栈顶)进行插入和删除的线性表,栈满需要进行扩容操作
- 链栈,栈顶一般放在单链表的头部,一般不需要设置头结点,添加到栈底的第一个元素指针域为null,之后每一个指针域都指向上一个添加的元素
队列
-
特点
- 先进先出(FIFO,队尾入队头出),只能在一端(tail,elements.length-1 处)进行插入元素,而在另一端(head,索引为0处)进行删除元素操作。(头尾相接的队列称为循环队列)
- 队列满的条件是
(tail+1)%QueueSize==head
- 通用计算队列长度的公式
(tail-head+QueueSize)%QueueSize
-
队列添加删除的细节
- head 与 tail 是用来标记队列的指针。空队列时,两指针同时位于线性表索引为0处
- 队列特点是(假设线性表索引是从左至右),添加元素,元素从队列右侧进入,tail++,tail向右移1位;删除元素,元素从左侧取出,head++,head 向右移1位,索引为0处值为null。
线性 与 链式结构 比较
- 不同
- 线性数据结构,初始化指定
Capacity(容量)
,查找根据索引查找,时间复杂度为O(1);增删需要调整各元素的位置,时间复杂度为O(n) - 链式数据结构,增删元素时间复杂度为O(1);指定索引处增删时间复杂度为O(n),因为需要进行遍利,同理查找元素的复杂度为O(n),链式数据结构没有容量限制,但是内存是有限的
- 线性数据结构,初始化指定
堆 与 队列 相互转换
-
原理:堆与队列是线性表与链表的不同逻辑结构实现,物理存储结构都是基于线性表或链表
-
结构转换
- 堆栈的栈顶(即元素进出的位置),可以当作队列的头部;堆栈的栈底,可以当作队列的尾部
-
转换源码细节(强烈推荐去查阅API)
- 线性结构,参考Java的
ArrayDeque
的增删操作 - 链式结构,参考Java的
LinkedList
的增删操作
- 线性结构,参考Java的