c++栈和队列（stack和queue）

本文主要是介绍c++栈和队列（stack和queue），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

栈和队列是两个极其相似的数据结构，栈具有先进后出的特性，队列具有先进先出的特性。今天我们就来简单的介绍一下栈和队列这两数据结构，其中队列我们介绍普通队列、双端队列（了解）和优先级队列（其实这就是堆这种数据结构），我们顺便再来认识一下标准库在实现这两数据结构时使用的容器适配器，它对我们实现代码的复用起到怎样的效果

stack

栈是一个先进后出的数据结构，c++标准库的实现可参考stack - C++ Reference (cplusplus.com)

功能上都不复杂，下面我们先不用容器适配器的方式模拟实现一个，我们可以以组合的方式就，在栈里内置一个顺序表，复用顺序表的实现

#include<vector>
namespace zzzyh
{template<class T>class stack{ public:stack() {}void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_back();}T& top() {return _c.back();}const T& top()const {return _c.back();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:std::vector<T> _c;};
}

queue

普通队列

普通队列和栈的功能类似，只不过它是先进先出的结构queue - C++ Reference (cplusplus.com)

功能上都不复杂，下面我们先不用容器适配器的方式模拟实现一个，我们可以以组合的方式就，在栈里内置一个链表，复用链表的实现

#include <list>
namespace zzzyh
{template<class T>class queue{public:queue() {}void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_front();}T& back() {return _c.back();}const T& back()const {return _c.back();}T& front() {return _c.front();}const T& front()const {return _c.front();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:std::list<T> _c;};
}

优先级队列

前面我们介绍了优先级队列其实就是堆，在此基础上我们就来简单的认识一下优先级队列priority_queue - C++ Reference (cplusplus.com)

功能并不复杂，我们知道堆的底层是数组（顺序表），我们可以不使用容器适配器的方式实现，以组合的形式复用顺序表的实现。但这样的实现并不灵活，因为我们在底层可以复用其它的数据结构，不适应容器适配器更换底层的结构是极其复杂的。下面我们就先来学习一下什么是容器适配器，再来用容器适配器的方式实现我们的优先级队列

容器适配器

容器适配器是一种设计模式，它可以屏蔽底层实现的细节，只需要调用接口即可，这也是封装思想的一种实现。容器适配器和我们前面将类模板/函数模板时提到的类型参数类似，也是通过传递类型参数来实现底层复用不同的容器

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为
容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装

再谈stack和queue

下面我们用容器适配器的方式重构我们的代码

stack

#pragma once
//#include <deque>
#include <list>
#include <vector>namespace zzzyh
{template<class T,class Container = std::vector<T>>class stack{public:stack() {}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() {return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

queue

queue包含普通队列和优先级队列

普通队列

#pragma once
#include <list>
#include <vector>
//#include <deque>namespace zzzyh
{template<class T, class Container = std::list<T>>class queue{public:queue() {}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front() {return _con.front();}const T& back() {return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};}

优先级队列

#pragma once
#include <vector>
//#include <algorithm>namespace zzzyh
{template<class T>class Less{public:bool operator()(const T& t1, const T& t2){return t1 < t2;}};template<class T>class Greate{public:bool operator()(const T& t1, const T& t2){return t1 > t2;}};template<class T, class Container = std::vector<T>,class Com = Less<T>>class priority_queuq{public:void push(const T& x){_con.push_back(x);xiangshangtiaozheng(size() - 1);}const T& top(){return _con.front();}void pop(){std::swap(_con.front(), _con.back());_con.pop_back();xiangxiatiaozheng(0,size());}size_t size(){return _con.size();}bool empty() {return _con.empty();}private:Container _con;void xiangshangtiaozheng(int i) {Com com;while (i > 0 && com(_con[i], _con[(i - 1) / 2])) {std::swap((_con[i]), (_con[(i - 1) / 2]));i = (i - 1) / 2;}}void xiangxiatiaozheng( int i, int sz) {Com com;while (i * 2 + 1 < sz) {int chile = i * 2 + 1;if (chile + 1 < sz && com(_con[chile + 1], _con[chile])) {chile++;}if (com(_con[chile],_con[i] )) {std::swap(_con[i], _con[chile]);i = chile;}else return;}}};}

再谈优先级队列

堆的相关算法

其实，在algorithm这个算法和容器相关的头文件里包含了一些关于堆的算法

仿函数

前面我们对于升序降序都是写死的，如果我们需要自定义排序方式需要使用到仿函数

仿函数（Functor）是一种能行使函数功能的类，它重载了`operator()`，使得类对象可以像函数一样调用。在C++中，仿函数常用于提高代码复用性和资源管理，尤其是在STL中。仿函数可以避免全局变量，提供更好的封装和扩展性，且可结合模板技术和其他编程思想。

这时我们就可以用仿函数实现比较大小

template<class T>class Less{public:bool operator()(const T& t1, const T& t2){return t1 < t2;}};template<class T>class Greate{public:bool operator()(const T& t1, const T& t2){return t1 > t2;}};

再将仿函数传递给容器，容器就可以按照我们的想法排序

双端队列（deque）

我们在倒回去观察一下标准库实现时的模板

我们发现标准库在实现时默认底层使用的是deque，我们就来简单的认识一下这个双端队列

我们知道顺序表和链表互为补充，它们的优缺点互为补充，那么是否有一种数据结构可以既有顺序表的优点也有链表的优点呢，双端队列就在这种美好的憧憬下诞生了，但双端队列只有在特定场景下使用，并不能完全代替顺序表和链表的功能

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端
进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与
list比较，空间利用率比较高。

双端队列（deque）是队列的一种变形，一般队列只能在队尾添加元素（push），在队首删除元素（pop），双端队列则同时在队首或者队尾执行添加和删除工作。C++中，使用双端队列需要包含头文件<deque>。C++中队列的基本操作如下：

push_back()：在队列尾部添加元素，无返回值。这个操作跟普通队列（queue）的push()方法类似，在队列的尾部添加一个元素；
push_front()：在队列头部添加元素，无返回值；
pop_back()：删除队列尾部的元素，无返回值；
pop_front()：删除队列头部的元素，无返回值；
front() ：获得队列头部元素。此函数返回值为队列的头部元素，常与pop_front()函数一起，先通过front()获得队列头部元素，然后用pop_front()将其从队列中删除；
back()：获得队列尾部元素。此函数返回值为队列的尾部元素，常与pop_back()函数一起，先通过back()获得队列头部元素，然后用pop_back()将其从队列中删除；
size()：获得队列大小。此函数返回队列的大小，返回值是“size_t”类型的数据，“size_t”是“unsigned int”的别名；
empty() ：判断队列是否为空。此函数返回队列是否为空，返回值是bool类型。队列空：返回true；不空：返回false。

更多介绍，可以参考deque - C++ Reference (cplusplus.com)使用详解。

至于其底层实现，是靠迭代器维护的，相对比较复杂，今天就不在这里展开，我们只介绍其特性和使用

优缺点

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩
容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段

deque有一个致命缺陷：不适合遍历，前面我们也介绍了底层是靠迭代器维护的，遍历时迭代器需要频繁校验合法性

在实际中使用线性结构时，大多数情况下优先考虑vector和list，queue的一大实际使用就是vector和list的默认底层实现，这是因为stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。