04-数据结构/02-queue与deque

queue（队列）

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

定义

queue<int> q;

常用操作

操作	说明
q.push(x)	将 x 放入队尾
q.pop()	弹出队头元素
q.front()	返回队头元素
q.back()	返回队尾元素
q.size()	返回元素数量
q.empty()	判断是否为空

示例

queue<int> q;
q.push(1);
q.push(2);
q.push(3);

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

deque（双端队列）

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

定义

deque<int> q;

常用操作

操作	说明
q.push_back(x)	从末尾放入 x
q.push_front(x)	从开头放入 x
q.pop_back()	从末尾弹出元素
q.pop_front()	从开头弹出元素
q.front()	返回队头元素
q.back()	返回队尾元素
q[pos]	访问下标为 pos 的元素
q.clear()	清空
q.size()	返回元素数量
q.empty()	判断是否为空

双端队列 vs vector

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