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

什么是栈？什么是队列？

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

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

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

栈与队列

栈：

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) { // 出队后链表为空，头节点和尾节点都置为 nullptr newHead = 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：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true



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

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 <= s.length <= 105s 仅由小写英文字母组成。

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; 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 <= 104tokens[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 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

示例 2：输入：nums = [1], k = 1 输出：[1]



提示：1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length

class Solution { private: struct myQueue{ // 手搓，单调队列 v private: 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 <= 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的



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

哒哒哒，后续补充

蓝桥真题

一、买二赠一

问题描述

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

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

输入格式

第一行包含一个整数 NN。

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

输出格式

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

样例输入



样例输出



样例说明

小明可以先购买价格 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 小于 2 if (k < 2) { k++; // 累加当前数组元素到总和中 sum += vec[i]; } // 如果 k 大于等于 2 if (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>

( •̀ ω •́ )✧点击这里，继续学习其他模块吧！