---
title: "队列"
created: 2025-11-28
tags:
  - 算法
---

# 队列

## 数组模拟

使用两个指针维护数组q

hh为队头 要做删除操作 以0为起点

tt为队尾 用于插入 和栈同理 以-1为起点

队尾（右边）加 队头（左边）删

入队：`q[++tt]=x`

出队：`hh++`

判空 `tt≥hh?"no":"yes"`

取队头`q[hh]`

## queue

```cpp
#include <queue>
std::queue<int> myQueue;
```

队列是一种类型的容器的适配器，FIFO（先进先出），其中元素被插入到所述容器的一端，并从其另一端进行提取操作。

队列被实现为容器的适配器，其是使用特定容器类封装到对象内部，作为其底层的容器类，提供了一个特定的一组成员函数来访问它的元素。

元素被压入到所指定容器的“后面”，并从其“前”弹出。

底层容器可以是标准容器类模板或一些其它专门设计的容器类中的一个。

这个基础容器应至少包括以下操作支持：

- empty
- size
- front
- back
- push\_back
- pop\_front

标准库容器中的deque和list满足上面的要求。对于没有指定容器的queue实例，默认情况下使用标准库容器deque。

1.队列初始化

```cpp
deque<int> mydeck(3, 100);        // 双端队列里初始化3个元素，都是100
list<int> mylist(2, 200);         // list 容器里初始化2个元素，都是200
queue<int> first;                 // 初始化一个空队列
queue<int> second(mydeck);        // 复制 mydeck 的内容初始化队列
queue<int, list<int> > third; // 初始化空队列，底层使用 list 容器
queue<int, list<int> > fourth(mylist);    // 复制 mylist 的内容初始化队列，底层使用 list 容器
cout << "size of first: " << first.size() << endl; // 0
cout << "size of second: " << second.size() << endl; // 3
cout << "size of third: " << third.size() << endl; // 0
cout << "size of fourth: " << fourth.size() << endl; // 2
```

2.判空

```cpp
queue<int> myqueue1;
bool empty1 = myqueue1.empty(); // true
queue<int> myqueue2({100,100});
bool empty2 = myqueue2.empty(); // false
```

3.获得元素个数

```cpp
queue<int> myints;
cout << "0. size: " << myints.size() << endl; // 输出：0
for (int i = 0; i < 5; i++) myints.push(i);
cout << "1. size: " << myints.size() << endl; // 输出：5
myints.pop();
cout << "2. size: " << myints.size() << endl; // 输出：4
```

4.返回头元素引用

头元素就是最先加入队列的元素，这个元素也是下次pop出队的元素。

```cpp
queue<int> myqueue3;
myqueue3.push(77);
myqueue3.push(66);
int& a1 = myqueue3.front(); // 77
int a2 = myqueue3.front(); // 77
myqueue3.front() = 88; // 给头元素77赋值为88
cout << "front:" << myqueue3.front() << endl; // 输出：88
```

5.返回末尾元素引用

末尾元素就是最后加入队列的元素，这个元素也是最新push入队的元素。

```cpp
queue<int> myqueue4;
myqueue4.push(77);
myqueue4.push(66);
int& b1 = myqueue4.back(); // 66
int b2 = myqueue4.back(); // 66
myqueue4.back() = 33; // 给末尾元素66赋值为33
cout << "front:" << myqueue4.front() << endl; // 输出：33
```

6.入队/出队

```
queue<int> myqueue5;
myqueue5.push(55); // 无返回值，入队了一个55，size()==1
myqueue5.push(45); // size()==2
myqueue5.pop(); // 无返回值，出队了一个55，size()==1
```

7.(C++11)另一种入队，其底层容器调用了emplace\_back方法。

```
myqueue5.emplace(45);
```

8.(C++11)交换

```cpp
queue<int> teeth;
teeth.emplace(4); teeth.emplace(7);
queue<int> bags;
bags.emplace(4); bags.emplace(7); bags.emplace(7);
bags.swap(teeth);
cout << teeth.size() << endl; //输出：3
cout << bags.size() << endl; //输出：2
```

9.运算符 = != > >= < <=

```cpp
// [==]当两个队列front()内容一致，返回true
queue<int> q1, q2;
bool ret = q1 == q2; // ret为true

// [!=]当两个队列元素front()不相等，返回true
queue<int> q3, q4;
q3.push(1);
bool ret2 = q3 != q4; // ret2为true

// [>]左边队列的front()的元素大于右边队列pop的元素，则返回true.
queue<int> q5, q6;
q5.push(1); q5.push(2); q5.push(2);
q6.push(0); q6.push(2);
bool ret3 = q5 >= q6; // ret3为true，因为1大于0
```

## 题目：

- [[2-Learning/02-算法/03-刷题理模型/双指针相关模型/前后指针/品种临近|品种临近]]
- [[机器翻译|机器翻译]]

- [[time needed to buy tickets|time needed to buy tickets]]
- [[公交换乘|公交换乘]]

- [[小组队列|小组队列]]
- [[海港|海港]]
- [[逛画展|逛画展]]

- [[插松枝|插松枝]]
- [[包装机|包装机]]

- [[2-Learning/02-算法/03-刷题理模型/多路归并相关问题/蚯蚓|蚯蚓]]
- [[（未解决）双端队列|（未解决）双端队列]]

### 更多题目：

- [动物收容所](https://leetcode-cn.com/problems/animal-shelter-lcci/)
- [最近的请求次数](http://leetcode-cn.com/problems/number-of-recent-calls/)
- [剑指 Offer II 042. 最近请求次数](http://leetcode-cn.com/problems/H8086Q/)
- [剑指 Offer II 041. 滑动窗口的平均值](http://leetcode-cn.com/problems/qIsx9U/)

---
⬅️ [[栈与队列相关模型|栈与队列相关模型]] 🏠 [[00-刷题理模型]] ➡️ [[time needed to buy tickets|time needed to buy tickets]]