查看“︁04-数据结构/02-queue与deque”︁的源代码


== queue（队列） ==

队列是一种'''先进先出（FIFO）'''的数据结构。

=== 定义 ===

<syntaxhighlight lang="cpp">
queue<int> q;
</syntaxhighlight>

=== 常用操作 ===

{| class="wikitable"
! 操作 !! 说明
|-
| <code>q.push(x)</code>
| 将 <code>x</code> 放入队尾
|-
| <code>q.pop()</code>
| 弹出队头元素
|-
| <code>q.front()</code>
| 返回队头元素
|-
| <code>q.back()</code>
| 返回队尾元素
|-
| <code>q.size()</code>
| 返回元素数量
|-
| <code>q.empty()</code>
| 判断是否为空
|}

=== 示例 ===

<syntaxhighlight lang="cpp">
queue<int> q;
q.push(1);
q.push(2);
q.push(3);

while (!q.empty())
{
    cout << q.front() << " "; // 输出 1 2 3
    q.pop();
}
</syntaxhighlight>

== deque（双端队列） ==

双端队列可以在'''两端'''进行插入和删除。

=== 定义 ===

<syntaxhighlight lang="cpp">
deque<int> q;
</syntaxhighlight>

=== 常用操作 ===

{| class="wikitable"
! 操作 !! 说明
|-
| <code>q.push_back(x)</code>
| 从末尾放入 <code>x</code>
|-
| <code>q.push_front(x)</code>
| 从开头放入 <code>x</code>
|-
| <code>q.pop_back()</code>
| 从末尾弹出元素
|-
| <code>q.pop_front()</code>
| 从开头弹出元素
|-
| <code>q.front()</code>
| 返回队头元素
|-
| <code>q.back()</code>
| 返回队尾元素
|-
| <code>q[pos]</code>
| 访问下标为 <code>pos</code> 的元素
|-
| <code>q.clear()</code>
| 清空
|-
| <code>q.size()</code>
| 返回元素数量
|-
| <code>q.empty()</code>
| 判断是否为空
|}

=== 双端队列 vs <code>vector</code> ===

- <code>deque</code> 可以在前方高效插入删除
- <code>deque</code> 也可以按下标访问
- 但 <code>deque</code> 的按索引访问比 <code>vector</code> 稍慢


[[Category:数据结构]]
[[Category:三三文档]]