1. queue 介绍及使用方法
queue是 C++ 标准模板库(STL)中的容器适配器,遵循先进先出(FIFO)原则。它基于其他容器(如deque或list)实现,仅允许在队尾插入元素,在队头删除元素。
queue 的底层通常是一个 deque<T>(双端队列),虽然 deque 是可以从两端来进行操作的,但是我们只要只提供一端的接口,那么就可以来把它当做 queue 来使用。
因为 queue 需要支持高效的'队尾插入'(push)和'队头删除'(pop)操作,而 deque 的 push_back(尾插)和 pop_front(头删)操作均能在常数时间内完成,且无需像 vector 那样在头删时移动大量元素,也无需像 list 那样维护额外的指针开销,综合性能更优。
2. queue 的常用函数
| 函数名 | 函数作用 |
|---|---|
| void push(const T& x) | 在尾部插入元素 |
| void pop() | 移除头部元素 |
| T& front() | 返回头部元素 |
| T& back() | 返回尾部元素 |
| size_t size() | 返回队列的大小 |
| bool empty() | 判断是否为空,为空就返回 true |
3. 模板参数说明
在这里写两个 class 是为了方便使用,这两个模板参数实际上是各司其职,只是语法上要求写在同一个 template<> 里,使用时会根据场景自动匹配对应的参数。
前面的 T 是明确指定队列中元素的类型(比如 int、string 等),这是队列对外提供的'数据类型契约'—— 队列里只能存 T 类型的东西。后面的 Container 是指定用什么容器来存储这些 T 类型的元素,而默认的 deque<T> 就是'用双端队列来存 T 类型元素'的意思。
PS:只写后面那一个理论上来说也是可以的,但是会让用户使用门槛变高,比如想声明一个存 int 的队列,用户不能直接写 queue<int>,而必须写成 queue<deque<int>>(如果想用默认容器),或者 queue<vector<int>>。这会让接口变得不直观——用户需要先知道底层容器的类型,才能正确声明队列,违背了'队列是容器适配器,用户无需关心底层实现'的设计初衷。
PS:只写前面哪一个是不行的,如果只写 template<class T>,就意味着用户无法指定底层容器了——因为没有 Container 这个参数来接收用户自定义的容器类型。
template<class T, class Container = deque<T>>
4. 私有成员变量
这就是申明一个私有成员 _con。
: Container _con;


