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

什么是栈？什么是队列？

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

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

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

栈与队列

栈：

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<<\"空栈\"<val; head = head->next; delete temp; return cur; } // 取元素 int top(){ if(empty()){ cout<<\"空栈\"<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 // 基于链表来实现队列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 << \"队列为空，无法出队\" <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 << \"队列为空，无法获取队首元素\" <val; }};

竞赛中如何运用

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

但是怎么用呢？

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

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

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

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

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

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

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

/stæk/

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

#include #include using namespace std;int main(){ stack 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> s2; s2.push(1); s2.push(2); s2.pop(); cout<<s2.top(); while(!s2.empty()){ cout<<s2.top(); s2.pop(); } return 0;}

/kjuː/

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

#include #include using namespace std;int main(){ queue 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 1myQueue.pop(); // return 1, queue is [2]myQueue.empty(); // return false

提示：

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

class MyQueue {private: stack s1; stack s2;public: // 推入 void push(int val){ s1.push(val); } // 交换函数 void Swap(stack& s1, stack& 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(); // 返回 2myStack.pop(); // 返回 2myStack.empty(); // 返回 False

提示：

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

class MyStack {private: queue q1; queue q2;public: // 压入元素 void push(int val){ q1.push(val); } // 交换元素 void Swap(queue& q1, queue& 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 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 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 s;public: int evalRPN(vector& 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] <= 104
• 1 <= k <= nums.length

class Solution {private: struct myQueue{ // 手搓，单调队列 v private: deque 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 maxSlidingWindow(vector& nums, int k) { vector 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​。

输出格式

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

样例输入

71 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 que = new LinkedList(); int k = 0; long sum = 0; // 遍历排序后的数组 for (int i = 0; i = vec[i]) { // 移除队列头部元素 que.poll(); continue; } // 如果 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 #include #include #include #define ll long longusing namespace std;// 重点在于，queue这种辅助空间，不会轻易被想到bool cmp(ll a, ll b){ return a>b;}int main(){ // 理智，一点 int n; cin>>n; vector vec(n); for(int i=0; i>vec[i]; sort(vec.begin(),vec.end(),cmp); // 排序 queue que; int k=0; ll sum=0; for(int i=0; i=vec[i]){ que.pop(); continue; } if(k=2){ que.push(vec[i]/2); k=0; } } cout<<sum<<endl; return 0;}

知识点

1、析构函数的作用

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

2、C++标准库 /dek/

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

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

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

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

#include #include using namespace std;int main(){ deque 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++ 标准库 

5、C++ 容器类

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