【STL】| C++ 栈和队列（详解、容器适配器的初步引入）

目录

前言

总代码

容器适配器的引入

栈 stack

队列 queue

栈和队列用法简介

栈

队列

deque简介（了解即可）

结语

---

前言

今天我们要讲解的结构是栈和队列

这两个的具体实现相比于前面我们学的string、vector、list都要简单得多（因为容器适配器的引入）

如果有需要了解这两个数据结构的具体函数用法的话，也可以在较为官方的网站上进行查阅，如下

https://legacy.cplusplus.com/reference/stack/stack/?kw=stack

总代码

如果有友友只是复习需要，只想看完整代码的话，可以直接点下面的gitee链接

当然对于看完了整篇文章的友友也可以照着这里的代码敲一篇进一步理解喔...(*￣０￣)ノ

gitee - stack & queue - blog - 2024-08-08

容器适配器的引入

在之前，我们实现的数据结构都是使用的迭代器，但是今天这两个并不是使用迭代器的，因为栈和队列这两个就是插入数据，拿出数据，出栈、出队列，并没有遍历一遍我看看里面的数据一说

所以我们今天会用到一个容器适配器

什么是容器适配器呢？

现象上来看就是一个函数模板上面的参数，我们将已经存在的数据结构如vector、list、deque等作为模板供类使用

就拿栈来举例子吧，试想一下，我们的栈就是一个入栈、出栈

而这两个动作在我们的vector里就是尾插、尾删

同样的，什么empty、size、top（就是vector里面的back），都能使用这些函数的功能，所以我们就不需要自己写，我们只需要使用这些已存在的容器即可

举个例子：

template<class T, class container = vector<T>>

而我们的类，内部的成员就可以是 container _con;

栈 stack

如上所述，我们直接上代码：

#include<iostream>
using namespace std;
#include<vector>namespace hjx
{template<class T, class container = vector<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:container _con;};
}

我们可以看到，全程都是使用我们容器适配器的功能在复用过来实现我们的栈

这里有一点值得一提的是，我们的栈不仅仅可以用vector作为适配器，用list或者一个叫做deque的容器也可以，因为只要有尾插尾删（高效的前提下），就能被用来实现栈

队列 queue

先上代码：

#include<iostream>
using namespace std;
#include<list>namespace hjx
{template<class T, class container = list<T>>class queue{public: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();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:container _con;};
}

我们可以看到，list和stack大部分地方都是相似的，唯一不同的两点就在于：

1. 适配器容器stack可以使用vector，但是队列不行，因为vector的头删要挪动数据效率低
2. queue没有top，而是front和back

栈和队列用法简介

栈

栈符合的原理是后进先出，图示如下：

栈最常用的就是入栈、出栈，如果要将全部数据取出来的话，就写一个while循环判断栈是否为空（empty），然后挨个取  top()，出栈

代码如下（仅展示最常用的）：

void test_stack1()
{stack<int> s1;s1.push(1);s1.push(2);s1.push(3);s1.push(4);while (!s1.empty()){cout << s1.top() << " ";s1.pop();}
}

队列

队列和栈同理，就是入队列，出队列

只不过和栈不同的点在于，栈是后进先出，队列是先进先出，图示如下：

而如果要将数据全部取出来的话，我们同样需要写一个while循环判断是否为空，然后取对头，出队列

代码如下（仅展示最常用的）：

void test_queue1()
{queue<int> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);q1.push(5);while (!q1.empty()){cout << q1.front() << " ";q1.pop();}
}

deque简介（了解即可）

其实，C++标准库里面，栈和队列这两个的默认容器适配器是deque（模板缺省参数那里）

template<class T, class container = deque<T>>

这就要谈到一段历史了，C++曾想要打造一个容器，让其既像vector也像list

这个容器就是deque

但可以看到，这个容器并没有实现得像想象中的那么好，不然都话我们现在也不会还在用vector和list了，如果成了，直接全部去学deque就好了

对于这个结构我们需要知道的就是，他只适用于仅需要头插头删，尾插尾删的情况

如果是有说要在中间动点手脚的话，这会涉及到一个数学的逻辑，和我们要学的技术就扯得有点远了

结语

这篇博客到这里，对栈和队列的讲解就结束啦(～￣▽￣)～

如果觉得对你有帮助的话，请务必多多支持博主喔<(＿　＿)>~(￣▽￣)~*