队列
定义
![队列](asset-img/queue-1.png)
![双端队列](asset-img/queue-2.png)
- 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行删除。允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。
- 因为先进入队列的成员总是先离开队列,队列亦称作先进先出(First In First Out)的线性表,简称FIFO表
ADT类型定义
- 数据对象:\(D=\{a_i | a_i \in ElemSet, i=1,2,...,n, n≥0 \}\)
- 数据关系:\(R1=\{\left \langle a_{i-1},a_i\right \rangle| a_{i-1},a_i \in D, i=2,...,n\}\) 约定 \(a_n\) 端为队列尾,\(a_1\) 端为队列头
-
基本操作
InitQueue(&Q)
- 操作结果:构造一个空队列
Q
。
- 操作结果:构造一个空队列
DestroyQueue(&Q)
- 初始条件:队列
Q
已存在。 - 操作结果:队列
Q
被销毁。
- 初始条件:队列
EnQueue(&Q, e)
- 初始条件:队列
Q
已存在。 - 操作结果:插入元素
e
为新的队尾元素
- 初始条件:队列
DeQueue(&Q, &e)
- 初始条件:队列
Q
已存在且非空。 - 操作结果:删除
Q
的队头元素,并用e
返回其值。
- 初始条件:队列
GetHead(Q, &e)
- 初始条件:队列
Q
已存在且非空。 - 操作结果:用
e
返回Q
的队头元素
- 初始条件:队列
QueueTraverse(Q,visit())
- 初始条件:队列
Q
已存在且非空,visit()
为元素的访问函数。 - 操作结果:依次对
Q
的每个元素调用函数visit()
。一旦visit()
失败,则操作失败。
- 初始条件:队列
ClearQueue(&Q)
- 初始条件:队列
Q
已存在。 - 操作结果:将
Q
清为空队列。
- 初始条件:队列
QueueEmpty(Q)
- 初始条件:队列
Q
已存在。 - 操作结果:若
Q
为空队列,则返回TRUE
,否则返回FALSE
。
- 初始条件:队列
QueueLength(Q)
- 初始条件:队列
Q
已存在。 - 操作结果:返回
Q
中元素个数,即队列的长度。
- 初始条件:队列
存储结构
顺序队列
循环静态顺序队列
- 最大限度的利用数组空间
- 出入队列时修改指针注意对maxsize取余
- 初始化建空队列时,令 front=rear=0;
- 每当插入一个新的队尾元素后,尾指针 rear增1;
- 每当删除一个队头元素之后,头指针front增1。
- 队列中一共有 \((rear+Maxsize-front) \% Maxsize\) 个元素
- 判满:
(Q.rear+1)%maxsize==Q.front
-
基本操作的实现(循环的顺序队列)
链队列
- 队列的链式存储结构简称为链队列,它是限制仅在表头删除和表尾插入的单链表。
-
结构定义
-
基本操作的实现
构造一个空队列 Q
销毁队列 Q
在当前队列的尾元素之后,插入元素 e 为新的队列尾元素
应用
树的层次遍历
核心思想
每次出队一个元素,就将该元素的孩子节点加入队列中,直到队列中元素个数为0时,出队的顺序就是该二叉树的层次遍历结果。
c++代码写法
vector<vector<int>> levelOrder(TreeNode *root) {
if (root == nullptr) return {};
vector<vector<int>> ans;
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
vector<int> vals;
for (int n = q.size(); n--;) {
// 取出队首元素
auto node = q.front();
q.pop();
// 加入至结果集
vals.push_back(node->val);
// 推入非空左孩子
if (node->left) q.push(node->left);
// 推入非空右孩子
if (node->right) q.push(node->right);
}
ans.emplace_back(vals);
}
return ans;
}
图的广度优先遍历
具体算法见图 > 图的广度优先遍历章节。使用了队列+辅助标记数组的方法。