【数据结构】栈与队列：基础 + 竞赛高频算法实操（含代码实现）

什么是栈？什么是队列？

什么是先进后出？什么是先进先出？

了解基础之后，又如何用来写算法题？

带着这些疑问，让我带领你，走进栈与队列的世界

栈与队列

栈：

1、栈的基本定义：

栈其实就是一种线性表，它只允许在固定的一段进行插入或者删除元素。

你可以把它想象成一个只能从上面开口放东西和拿东西的盒子。

那个能放东西和拿东西的上面开口的地方，我们就叫它栈顶。

2、栈的核心操作：入栈、出栈、取栈顶元素

3、栈的特性：先进后出（LIFO，Last In First Out）

什么意思呢？

就拿枪的弹夹来举例，把（栈）比作弹夹，把（元素）类比为子弹。

当你往弹夹里压子弹的时候，最后压进去的那颗子弹，会在最上面，

等开枪的时候，它会第一个被打出去。

而最开始压进去的子弹，因为被后来的子弹压在下面了，

所以是最后才被打出来的。

这就是先进后出

队列：

1、队列的基本定义：

队列本质上也是一种特殊的线性表。

它就像我们在排队一样，只允许在队伍尾部（队尾）加人（元素），只有队伍的最前排（队首）人（元素）才能离开。

2、队列的核心操作：入队列、出队列、取出队首元素。

3、队列的特性：先进先出（FIFO，First In First Out）

什么意思呢？

就像火车过隧道的例子，火车头就是队首，火车尾就是队尾。

火车进隧道的时候，车头先进入隧道，等出隧道的时候，也是车头先出来，

车尾后进去所以就后出来。

这就跟队列里的元素一样，先进入队列的元素会先出队列，后进入的就后出队列。

深度思索

上方只能让你浅显的了解各个函数的表层含义，它和咱们计算机还是不搭边的。

那他们在计算机中，那些场景会用到这些呢？

栈：

最典型的就是嵌套结构管理

• 括号匹配：遇到 (){} 等符号时，会将左括号，压入栈中，当遇到右括号时，判断栈中括号是否匹配。
• 调用函数：程序调用函数时，会把当前位置压栈保存，等函数执行完毕之后再按逆序返回。

栈在算法中的常见应用

• 表达式求值（中缀转后缀表达式）
• 浏览器后退 / 前进功能
• 迷宫寻路算法（深度优先搜索 DFS）

队列：

• 任务公平调度，多个程序排队等待CPU处理，按顺序执行避免混乱。
• 异步通信桥梁，微信发消息时，消息先入队列，对方手机再按顺序接收，避免同步压力

队列在算法中的常见应用

• 广度优先搜索（BFS）
• 消息队列系统（Kafka/RabbitMQ）
• 缓存淘汰策略（FIFO 算法）

栈与队列的算法实现

栈的实现：

栈最常用的四个函数，放入、弹出、取栈顶元素、判断是否为空

基于顺序表实现栈：

const int max_size = 100;
struct MyStack{
private:int arr[max_size];int size;
public:// 初始化MyStack():size(0){};// 放入void push(int val){if(size>max_size-1){cout<<"已抵达最大容量"<<endl;}arr[size]=val;size++;}// 弹出int pop(){if(empty()){cout<<"暂无数据，弹出失败"<<endl;return 0;}int cur = arr[size-1];size--;return cur;}int top() {if (empty()) {cout << "该栈为空栈" << endl;return 0;}int cur = arr[size-1];return cur;}bool empty(){if(size<=0) return true;else return false;}
};int main(){return 0;
}

基于链表实现栈：

struct Node{
public:int val;Node* next;Node():val(0),next(nullptr){}Node(int val):val(val),next(nullptr){}
};struct MyStack{
private:// 链表头指针Node* head; // 不同的色彩，我也想见一见
public:~MyStack(){while(head){Node* temp = head;head = head->next;delete temp;}}MyStack():head(nullptr){}// 入栈void push(int val){Node* cur = new Node(val);cur->next = head;head = cur;}// 出栈int pop(){if(empty()){cout<<"空栈"<<endl;return 0;}Node* temp = head;int cur = temp->val;head = head->next;delete temp;return cur;}// 取元素int top(){if(empty()){cout<<"空栈"<<endl;return 0;}return head->val;}// 判断是否为空bool empty(){return head == nullptr;}};

队列的实现：

基于顺序表实现队列

// 基于数组，实现的循环队列
const int CAPACITY = 100;
struct MyQueue{
private:int data[CAPACITY];int head;int tail;int count;
public:MyQueue():head(0),tail(0),count(0){}// 入队列void push(int val){if(count>=CAPACITY){cout<<"队列已满"<<endl;return;}data[tail] = val;tail = (tail+1)%CAPACITY;count+=1;}// 出队列int pop(){if(empty()){cout<<"空队列"<<endl;return 0;}int cur = data[head];head=(head+1)%CAPACITY;count--;return cur;}// 取队首元素int top(){if(empty()){cout<<"空队列"<<endl;return 0;}int cur = data[head];return cur;}// 判断是否为空bool empty(){return !count;}
};

基于链表实现队列

#include <iostream>// 基于链表来实现队列
class MyQueue{
private:// 定义链表节点的结构体struct Node {int val;  // 节点存储的值Node* next;  // 指向下一个节点的指针// 节点的构造函数，用于初始化节点的值Node(int val) : val(val), next(nullptr) {}};Node* newHead;  // 链表的头节点指针Node* newTail;  // 链表的尾节点指针public:// 队列的构造函数，初始化头节点和尾节点指针为 nullptr，表示队列为空MyQueue() : newHead(nullptr), newTail(nullptr) {}// 析构函数，用于释放链表中所有节点的内存，防止内存泄漏~MyQueue() {while (newHead) {Node* temp = newHead;newHead = newHead->next;delete temp;}}// 1. 入队列，就是尾插，为了和 Java 库中的队列保持一致，用 bool 返回值bool offer(int val) {// 创建一个新的节点，存储要插入的值Node* newNode = new Node(val);// 特殊情况处理：如果链表为空if (newHead == nullptr) {// 新节点既是头节点也是尾节点newHead = newNode;newTail = newNode;} else {// 一般情况处理：将新节点插入到链表尾部newTail->next = newNode;// 更新尾节点指针指向新的尾节点newTail = newTail->next;}return true;}// 2. 出队列，就是头删，注意头删也是要返回那个要删除的值int poll() {// 特殊情况处理：链表为空，没得删if (newHead == nullptr) {std::cout << "队列为空，无法出队" << std::endl;return -1;  // 这里用 -1 表示出队失败，可根据实际情况修改}// 保存要出队的值int ret = newHead->val;Node* temp = newHead;// 链表只有一个元素的情况if (newHead->next == nullptr) {// 出队后链表为空，头节点和尾节点都置为 nullptrnewHead = nullptr;newTail = nullptr;} else {// 一般情况处理：更新头节点指针指向下一个节点newHead = newHead->next;}// 释放被删除节点的内存delete temp;return ret;}// 3. 取队列首元素int top() {// 特殊情况处理：链表为空，没得取if (newHead == nullptr) {std::cout << "队列为空，无法获取队首元素" << std::endl;return -1;  // 这里用 -1 表示获取失败，可根据实际情况修改}// 一般情况处理：返回头节点的值return newHead->val;}
};

竞赛中如何运用

其实这才是很多人关心的问题！毕竟学了，就是为了用！

但是怎么用呢？

总不能每次用到栈和队列时，都手敲实现吧？那太抽象了点！

所以，我们这里就引入了STL库中的<stack>与<queue>两个函数库

先简单的说一下，拓展一下认知：

栈与队列 是 以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈与队列的功能）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

那么问题来了，STL 中栈是用什么容器实现的？

从下图中可以看出，栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

<stack> /stæk/

• 栈顶插入(push)
• 栈顶弹出(pop)
• 栈顶获取元素(top)
• 判断是否为空(empty)

#include <iostream>
#include <stack>
using namespace std;int main(){stack<int> s1;s1.push(1);s1.push(2);s1.pop();cout<<s1.top();while(!s1.empty()){cout<<s1.top();s1.pop();}cout<<endl;// ==== 作为容器适配器 ====stack<int,deque<int>> s2;s2.push(1);s2.push(2);s2.pop();cout<<s2.top();while(!s2.empty()){cout<<s2.top();s2.pop();}return 0;
}

<queue> /kjuː/

• 插入(push)
• 删除(pop)
• 获取队首(front)
• 获取队尾(back)
• 判断非空(empty)

#include <queue>
#include <iostream>
using namespace std;
int main(){queue<int> q1;q1.push(1);q1.push(2);q1.push(3);// 首cout<<q1.front()<<endl;// 尾cout<<q1.back()<<endl;// 循环取出while(!q1.empty()){cout<<q1.front()<<endl;q1.pop();}return 0;
}

大纲

基础

一、用栈实现队列-（解析）-基础

二、用队列实现栈-（解析）-基础

三、有效的括号-（解析）-栈的基础应用

四、删除字符串中的所有相邻重复项-（解析）-栈的基础应用

五、 逆波兰表达式求值-（解析）-栈的基础应用

 六、滑动窗口最大值-（解析）-单调栈的基本应用

七、前 K 个高频元素-（解析）-

蓝桥真题

一、买二赠一-（解析）-将队列做为辅助空间

题目

基础练习

一、用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

class MyQueue {
private:stack<int> s1;stack<int> s2;
public:// 推入void push(int val){s1.push(val);}// 交换函数void Swap(stack<int>& s1, stack<int>& s2){while(!s1.empty()){s2.push(s1.top());s1.pop();}}// 移除int pop(){Swap(s1,s2);int cur = s2.top();s2.pop();Swap(s2,s1);return cur;}// 返回开头元素int peek(){Swap(s1,s2);int cur = s2.top();Swap(s2,s1);return cur;}// 判断非空bool empty(){return s1.empty();}};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

二、用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

class MyStack {
private:queue<int> q1;queue<int> q2;
public:// 压入元素void push(int val){q1.push(val);}// 交换元素void Swap(queue<int>& q1, queue<int>& q2){while(q1.size()>1){q2.push(q1.front());q1.pop();}}// 移除元素int pop(){ // 移除元素Swap(q1,q2);int val = q1.front();q1.pop();Swap(q2,q1);if(q2.size()!=0){q1.push(q2.front());q2.pop();}return val;}// 取出元素int top(){Swap(q1,q2);int val = q1.front();q2.push(val);q1.pop();Swap(q2,q1);if(q2.size()!=0){q1.push(q2.front());q2.pop();}return val;}// 判断非空bool empty(){return q1.empty();}};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

三、有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

class Solution {// 解决符号问题，就是stack的专场// 考虑的不够周全/*3种特殊情况右括号的情况：1、右括号的左边不是对应括号2、出现右括号，但是stack为空意外情况：1、字符串遍历完，仍然还有符号*/
public:bool isValid(string s) {stack<int> myStack;for(char c : s){if(c=='('||c=='['||c=='{') myStack.push(c);else{if(myStack.size()==0) return false;else {char ch = myStack.top();if(ch=='('&&c==')') myStack.pop();else if(ch=='['&&c==']')  myStack.pop();else if(ch=='{'&&c=='}')  myStack.pop();else return false;}}}if(myStack.size()!=0) return false;return true;}
};

四、删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. 1 <= s.length <= 105
2. s 仅由小写英文字母组成。

class Solution {// 相邻匹配问题，stack的专场stack<char> myStack; 
public:string removeDuplicates(string s) {for(char c : s){if(!myStack.empty() && myStack.top()==c) myStack.pop();else myStack.push(c);}string str="";while(!myStack.empty()){str+=myStack.top();myStack.pop();}reverse(str.begin(),str.end());return str;}
};

五、逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

• 1 <= tokens.length <= 104
• tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

class Solution {// 栈是符号表达式的专场stack<long long> s;
public:int evalRPN(vector<string>& tokens) {for(string str : tokens){if(str=="+"||str=="-"||str=="*"||str=="/"){int num2 = s.top(); s.pop();int num1 = s.top(); s.pop();if(str=="+") s.push(num1+num2);else if(str=="-") s.push(num1-num2);else if(str=="*") s.push(num1*num2);else s.push(num1/num2);}else s.push(stoll(str));}return s.top();}
};

六、滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

class Solution {
private:struct myQueue{ // 手搓，单调队列 vprivate:deque<int> myDeque;public:void push(int val){ // 放while(!myDeque.empty()&&myDeque.back()<val) myDeque.pop_back();myDeque.push_back(val);}void pop(int val){ // 弹出if(!myDeque.empty() && val==myDeque.front()) myDeque.pop_front();}int front(){ // 输出if(!myDeque.empty()) return myDeque.front();return 0;}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> vec;myQueue mq;for(int i=0; i<k; ++i) mq.push(nums[i]); // 存入vec.push_back(mq.front()); for(int i=k; i<nums.size(); ++i){mq.pop(nums[i-k]);mq.push(nums[i]);int val = mq.front();vec.push_back(mq.front());}return vec;}
};

七、前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

哒哒哒，后续补充

蓝桥真题

一、买二赠一

问题描述

某商场有 NN 件商品，其中第 ii 件的价格是 AiAi​。现在该商场正在进行 “买二赠一” 的优惠活动，具体规则是：每购买 22 件商品，假设其中较便宜的价格是 PP（如果两件商品价格一样，则 PP 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 P22P​ 的商品，免费获得这一件商品。可以通过反复购买 22 件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。

小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少钱？

输入格式

第一行包含一个整数 NN。

第二行包含 NN 个整数，代表 A1,A2,A3,…,ANA1​,A2​,A3​,…,AN​。

输出格式

输出一个整数，代表答案。

样例输入

7
1 4 2 8 5 7 1

样例输出

25

样例说明

小明可以先购买价格 44 和 88 的商品，免费获得一件价格为 11 的商品；再后买价格为 55 和 77 的商品，免费获得价格为 22 的商品；最后单独购买剩下的一件价格为 11 的商品。总计花费 4+8+5+7+1=254+8+5+7+1=25。不存在花费更低的方案。

评测用例规模与约定

对于 3030% 的数据，1≤N≤201≤N≤20。

对于 100100% 的数据，1≤N≤5×1051≤N≤5×105，1≤Ai≤1091≤Ai​≤109。

Java版：

import java.util.*;
// 重点在于Queue这种辅助空间，不易想到
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取输入的元素个数int n = scanner.nextInt();// 创建一个长整型数组来存储输入的元素long[] vec = new long[n];for (int i = 0; i < n; i++) {// 读取每个元素并存储到数组中vec[i] = scanner.nextLong();}// 对数组进行降序排序Arrays.sort(vec);reverseArray(vec);// 创建一个队列来存储处理后的元素Queue<Long> que = new LinkedList<>();int k = 0;long sum = 0;// 遍历排序后的数组for (int i = 0; i < n; i++) {// 如果队列不为空且队列头部元素大于等于当前数组元素if (!que.isEmpty() && que.peek() >= vec[i]) {// 移除队列头部元素que.poll();continue;}// 如果 k 小于 2if (k < 2) {k++;// 累加当前数组元素到总和中sum += vec[i];}// 如果 k 大于等于 2if (k >= 2) {// 将当前数组元素除以 2 后加入队列que.add(vec[i] / 2);k = 0;}}// 输出总和System.out.println(sum);scanner.close();}// 反转数组元素顺序以实现降序排序public static void reverseArray(long[] arr) {int left = 0;int right = arr.length - 1;while (left < right) {long temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}}
}

C++版：

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define ll long long
using namespace std;
// 重点在于，queue这种辅助空间，不会轻易被想到
bool cmp(ll a, ll b){return a>b;
}
int main()
{// 理智，一点int n;cin>>n;vector<ll> vec(n);for(int i=0; i<n; ++i) cin>>vec[i];sort(vec.begin(),vec.end(),cmp); // 排序queue<ll> que;int k=0;ll sum=0;for(int i=0; i<n; ++i){if(!que.empty()&&que.front()>=vec[i]){que.pop();continue;}if(k<2){k++;sum+=vec[i];}if(k>=2){que.push(vec[i]/2);k=0;}}cout<<sum<<endl;return 0;
}

知识点

1、析构函数的作用

• 自动调用：其作用是，在对象生命周期结束时自动释放资源，防止资源泄露。
• 怎么调用：类名(){...}前加上~，代表析构。
• 默认实现：未被显示定义，编辑器会自动生成一个空析构函数。

2、C++标准库<deque> /dek/

deque /dek/ 是标准模版库(STL)的一部分，他提供了双端队列（double-ended queue）的实现。

是一种允许，在两端进行插入和删除操作的线性数据结构。

并且<deque>的随机访问时间复杂度为O(1)。

不过deque 是由多个连续的存储块组成的，这些存储块在内存中不一定是连续的。只是随机访问的话，还是vector(头插O(n),尾插O(1))比较合适。

#include <iostream>
#include <deque>
using namespace std;
int main(){deque<int> myDeque;// 插入myDeque.push_back(3);myDeque.push_back(4);myDeque.push_front(2);myDeque.push_front(1);// 访问元素for(int i=0; i<myDeque.size(); ++i){cout<<myDeque[i]<<endl;}// 删除元素myDeque.pop_back();myDeque.pop_front();// 访问头部与尾部元素cout<<myDeque.front()<<endl;cout<<myDeque.back()<<endl;return 0;
}

---

借鉴博客：

1、数据结构：栈和队列(Stack & Queue)【详解】

2、栈和队列（详细版，一看就懂。包含栈和队列的定义、意义、区别，实现）

3、栈与队列理论基础

4、C++ 标准库 <stack>

5、C++ 容器类 <queue>

---