什么是栈？什么是队列？
了解先进后出与先进先出的概念，以及它们如何应用于算法题。
栈与队列
栈
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 库使用
其实这才是很多人关心的问题！毕竟学了，就是为了用！
但是怎么用呢？
总不能每次用到栈和队列时，都手敲实现吧？那太抽象了点！
所以，我们这里就引入了 STL 库中的与两个函数库
先简单的说一下，拓展一下认知：
栈与队列 是 以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈与队列的功能）。
所以 STL 中栈往往不被归类为容器，而被归类为 container adapter（容器适配器）。
那么问题来了，STL 中栈是用什么容器实现的？
从下图中可以看出，栈的内部结构，栈的底层实现可以是 vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。
- 栈顶插入 (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;
}
- 插入 (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;
}
算法实战
基础练习
一、用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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 <= 10^4``s 仅由括号 '()[]{}' 组成
class Solution {
public:
bool isValid(string s) {
stack<char> 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 <= 10^5``s 仅由小写英文字母组成。
class Solution {
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 = ... = 22
提示：1 <= tokens.length <= 10^4``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 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 <= 10^5``-10^4 <= nums[i] <= 10^4``1 <= 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 <= 10^5``k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
**进阶：**你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
// 哒哒哒，后续补充
蓝桥真题
一、买二赠一
问题描述
某商场有 N 件商品，其中第 i 件的价格是 Ai。现在该商场正在进行 '买二赠一' 的优惠活动，具体规则是：每购买 2 件商品，假设其中较便宜的价格是 P（如果两件商品价格一样，则 P 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 P/2 的商品，免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。
小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少钱？
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数，代表 A1,A2,A3,…,AN。
输出格式
输出一个整数，代表答案。
样例说明
小明可以先购买价格 4 和 8 的商品，免费获得一件价格为 1 的商品；再后买价格为 5 和 7 的商品，免费获得价格为 2 的商品；最后单独购买剩下的一件价格为 1 的商品。总计花费 4+8+5+7+1=25。不存在花费更低的方案。
评测用例规模与约定
对于 30% 的数据，1≤N≤20。
对于 100% 的数据，1≤N≤5×10^5，1≤Ai≤10^9。
Java 版：
import java.util.*;
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;
}
if (k < 2) {
k++;
sum += vec[i];
}
if (k >= 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;
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 是标准模版库 (STL) 的一部分，他提供了双端队列（double-ended queue）的实现。
是一种允许，在两端进行插入和删除操作的线性数据结构。
并且的随机访问时间复杂度为 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;
}
