Jackie's Blog
栈与队列
Jackie
  2025-07-31   2025-08-04  4.6k 字  19 分钟

栈与队列

在已有的数据结构知识基础上补充

基础知识

栈和队列是STL（C++标准库）里面的两个数据结构

三个最为普遍的STL版本：

  1. HP STL其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码
  2. P.J.Plauger STL由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的
  3. SGI STL由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高

栈提供push和pop等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器（iterator）。不像set或者map提供迭代器iterator来遍历所有元素

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

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

栈的内部结构，栈的底层实现可以是vector、deque或list，主要就是数组和链表的底层实现

image

常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构

deque是一个双向队列，只需封闭一端、仅开放另一端便可实现栈的逻辑

SGI STL中队列底层实现缺省情况下一样使用deque实现的

  • 指定vector为栈的底层实现的初始化语句
std::stack<int,std::vector<int>> third;//使用vector为底层容器的栈

队列中先进先出的数据结构同样不允许有遍历行为，不提供迭代器，SGI STL中队列一样是以deque为缺省情况下的底部结构

  • 指定list为栈的底层实现的初始化语句
std::queue<int,std::list<int>> third;//定义以list为底层容器的队列

所以STL队列也不被归类为容器，而被归类为container adapter（容器适配器）

用栈实现队列

232. 用栈实现队列

使用两个栈模拟队列——一个输入栈，一个输出栈

动画模拟以下代码：

queue.push(1);
queue.push(2);
queue.pop();//关注点1

queue.push(3);
queue.push(4);
queue.pop();
queue.pop();//关注点2

queue.pop();
queue.empty();

image

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，输出栈如果为空，就把进栈数据全部导入进来，再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据

进栈出栈均空则队列为空

class MyQueue {
public:
    stack<int> stackIn;
    stack<int> stackOut;
    MyQueue() {
        
    }

    void push(int x) {
        stackIn.push(x);
    }
    
    int pop() {
        if(stackOut.empty()){
            while(!stackIn.empty()){
                stackOut.push(stackIn.top());
                stackIn.pop();
            }
        }
        int result=stackOut.top();
        stackOut.pop();
        return result;
    }
    
    int peek() {//返回队列头部（front）的元素，但不移除它
        int result=this->pop();
        stackOut.push(result);
        return result;
    }
    
    bool empty() {
        return stackIn.empty()&&stackOut.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();
 */
  • 时间复杂度：O(1)
  • 空间复杂度：O(n)

一定要懂得复用，功能相近的函数要抽象出来，不要大量的复制粘贴，很容易出问题！

用队列实现栈

225. 用队列实现栈

使用两个队列模拟栈——另一个队列用来备份

把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1

动画模拟以下代码：

queue.push(1);
queue.push(2);
queue.pop();//关注点1

queue.push(3);
queue.push(4);
queue.pop();//关注点2

queue.pop();
queue.pop();
queue.empty();

image

class MyStack {
public:
    queue<int> que1;
    queue<int> que2;
    MyStack() {
        
    }
    
    void push(int x) {
        que1.push(x);
    }
    
    int pop() {
        int size=que1.size();
        size--;//保留最后一个元素
        while(size--){
            que2.push(que1.front());
            que1.pop();
        }
        int result=que1.front();//最后一个元素即返回的值
        que1.pop();
        que1=que2;
        while(!que2.empty()){
            que2.pop();
        }
        return result;
    }
    
    int top() {
        int size=que1.size();
        size--;
        while(size--){
            que2.push(que1.front());
            que1.pop();
        }
        int result=que1.front();
        que2.push(que1.front());//获取值后将最后一个元素加入que2以保持原结构
        que1.pop();
        que1=que2;
        while(!que2.empty()){
            que2.pop();
        }
        return result;
    }
    
    bool empty() {
        return que1.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();
 */
  • 时间复杂度：pop为O(n)，top为O(n)，其他为O(1)
  • 空间复杂度：O(n)

改进

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外）重新添加到队列尾部，此时再去弹出元素就是栈的顺序了

class MyStack {
public:
    queue<int> que;
    MyStack() {
        
    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int size=que.size();
        size--;
        while(size--){//队列头部元素（最后一个元素除外）重添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result=que.front();//此时弹出的元素顺序为栈的顺序
        que.pop();
        return result;
    }
    
    int top() {
        int size=que.size();
        size--;
        while(size--){
            que.push(que.front());
            que.pop();
        }
        int result=que.front();//此时获得的为栈顶元素
        que.push(que.front());
        que.pop();
        return result;
    }
    
    bool empty() {
        return que.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();
 */
  • 时间复杂度：pop为O(n)，top为O(n)，其他为O(1)
  • 空间复杂度：O(n)

有效的括号

20. 有效的括号

先分析好有哪几种不匹配的情况！！！

有三种不匹配的情况：

  1. 左方向的括号多余了导致不匹配

image

  1. 括号未多余，但括号类型没有匹配上

image

  1. 右方向的括号多余了导致不匹配

image

如图：

image

  1. 已经遍历完字符串，但栈不为空，说明有相应的左括号没有右括号来匹配，return false
  2. 遍历字符串匹配过程发现栈里没有要匹配的字符，return false
  3. 遍历字符串匹配过程栈已空，没有匹配的字符，说明有右括号没有找到相应的左括号，return false
  4. 字符串遍历完之后，栈空，说明全部匹配，return true

技巧：匹配左括号的时候右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2!=0){
            return false;
        }
        stack<char> stack;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                stack.push(')');
            }else if(s[i]=='{'){
                stack.push('}');
            }else if(s[i]=='['){
                stack.push(']');
            }else if(stack.empty()||stack.top()!=s[i]){
                return false;
            }else{
                stack.pop();
            }
        }
        return stack.empty();
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

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

1047. 删除字符串中的所有相邻重复项

栈的目的就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看是否遍历过相同数值的相邻元素，然后再去做对应的消除操作

image

弹出剩余元素后对字符串进行得到最终的结果

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> stack;
        for(int i=0;i<s.size();i++){
            char c=s[i];
            if(stack.empty()||c!=stack.top()){
                stack.push(c);
            }else{
                stack.pop();
            }
        }
        string result="";
        while(!stack.empty()){
            result+=stack.top();
            stack.pop();
        }
        reverse(result.begin(),result.end());
        return result;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

改进

  • 双指针法

slow初始为0，如果第一个和第二个就相等了，slow–，slow这个时候变成-1，string是不能继续索引的了，那么这个时候就直接把前面的给删除掉就行。如果不这样写，就不能避免掉删除掉两个之后，又有两个相邻在一起的情况了

class Solution {
public:
    string removeDuplicates(string s) {
        int slow=0;
        for(int fast=1;fast<s.size();fast++){
            if(slow<0||s[slow]!=s[fast]){
                s[++slow]=s[fast];
            }else{
                slow--;
            }
        }
        s.resize(slow+1);
        return s;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
  • 字符串直接作为栈
class Solution{
public:
    string removeDuplicates(string s){
        string result;
        for(char c:s){
            if(result.empty()||result.back()!=c){
                result.push_back(c);
            }else{
                result.pop_back();
            }
        }
        return result;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

空间复杂度：O(1)，取决于使用的语言提供的字符串类是否提供了类似「入栈」和「出栈」的接口

注意返回值不计入空间复杂度

  • 字符串

image

  • 头插：s.insert(s.begin(), ch);或s.insert(0, 1, ch);
  • 头删：s.erase(s.begin());或s.erase(0,1);

逆波兰表达式求值

150. 逆波兰表达式求值

逆波兰表达式相当于是二叉树中的后序遍历，本题中每一个子表达式得出一个结果，然后拿这个结果再进行运算，相当于相邻字符串消除的过程

image

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long>stack;//力扣修改了后台测试数据，需要用long long
        for(int i=0;i<tokens.size();i++){
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
                long long num1=stack.top();
                stack.pop();
                long long num2=stack.top();
                stack.pop();
                if(tokens[i]=="+"){
                    stack.push(num2+num1);
                }
                if(tokens[i]=="-"){
                    stack.push(num2-num1);
                }
                if(tokens[i]=="*"){
                    stack.push(num2*num1);
                }
                if(tokens[i]=="/"){
                    stack.push(num2/num1);
                }
            }else{
                stack.push(stoll(tokens[i]));
            }
        }
        long long result=stack.top();
        return result;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

stoll()：string to long long。作用是把一个字符串（std::string或C-style string）转换成一个long long类型的整数

string s="12345";
long long num=stoll(s);//num=12345

滑动窗口最大值

239. 滑动窗口最大值

单调队列

  1. 如何求一个区间里的最大值？

暴力遍历一遍的过程中每次从窗口中再找到最大的数值，显然是O(n×k)的算法

如果用一个大顶堆（优先队列）来存放这个窗口里的k个数字，这样就可以知道最大的最大值是多少了，但问题是这个窗口是移动的，而大顶堆每次只能弹出最大值，无法移除其他数值，造成大顶堆维护的不是滑动窗口里面的数值了，所以不能用大顶堆

堆

此时需要一个队列放进去窗口里的元素，随着窗口的移动队列也一进一出，每次移动之后队列告诉我们里面的最大值

class MyQueue{
public:
    void pop(int value){
    }
    void push(int value){
    }
    int front(){
        return que.front();
    }
};

每次窗口移动的时候，调用que.pop（滑动窗口中移除元素的数值），que.push（滑动窗口添加元素的数值），然后que.front()就返回我们要的最大值

  1. 已经排序之后的队列怎么能把窗口要移除的元素（这个元素可不一定是最大值）弹出呢？

只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列

  • 单调队列维护队列里的元素过程

image

设计单调队列的时候pop和push操作保持如下规则：

  1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
  2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

每次窗口移动的时候，只要访问que.front()就可以返回当前窗口的最大值

image

基于以上规则可实现如下queue代码：

class MyQueue{//单调队列（从大到小）
public:
    //使用deque来实现单调队列（queue在没有指定容器的情况下，deque就是默认底层容器）
    deque<int> queue;
    //每次弹出时比较当前要弹出数值是否等于队列出口元素数值，相等则弹出，同时pop之前判断队列当前是否为空
    void pop(int value){
        if(!queue.empty()&&value==queue.front()){
            queue.pop_front();
        }
    }
    //push数值大于入口元素数值，将队列后端数值弹出，直到push的数值小于等于队列入口元素的数值，这样可保持队列里数值单调从大到小
    void push(int value){
        while(!queue.empty()&&value>queue.back()){
            queue.pop_back();
        }
        queue.push_back(value);
    }
    //查询当前队列里的最大值，直接返回队列front即可
    int front(){
        return queue.front();
    }
};

deque是可以两边扩展的，而且deque里元素并不是严格的连续分布的

  • 题目代码
class Solution {
private:
    class MyQueue{
    public:
        deque<int> queue;
        void pop(int value){
            if(!queue.empty()&&value==queue.front()){
                queue.pop_front();
            }
        }
        void push(int value){
            while(!queue.empty()&&value>queue.back()){
                queue.pop_back();
            }
            queue.push_back(value);
        }
        int front(){
            return queue.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue queue;
        vector<int> result;
        for(int i=0;i<k;i++){
            queue.push(nums[i]);
        }
        result.push_back(queue.front());
        for(int i=k;i<nums.size();i++){
            queue.pop(nums[i-k]);
            queue.push(nums[i]);
            result.push_back(queue.front());
        }
        return result;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(k)

优先队列

对于”最大值“，优先队列（堆）的大根堆可以帮助我们实时维护一系列元素中的最大值

初始时将数nums的前k个元素放入优先队列中，每当向右移动窗口时可把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，此时这个值在数组nums中的位置出现在滑动窗口左边界的左侧。因此当后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，可以将其永久地从优先队列中移除

不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系可在优先队列中存储二元组(num,index)，表示元素num在数组中的下标为index

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>> q;
        for(int i=0;i<k;i++){
            q.emplace(nums[i],i);
        }
        vector<int>result={q.top().first};
        for(int i=k;i<nums.size();i++){
            q.emplace(nums[i],i);
            while(q.top().second<=i-k){
                q.pop();
            }
            result.push_back(q.top().first);
        }
        return result;
    }
};

前 K 个高频元素

347. 前 K 个高频元素

优先队列

优先队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列

而且优先队列内部元素是自动依照元素的权值排列，缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）

定义一个大小为k的大顶堆，每次移动更新大顶堆的时候，每次都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢？

而且使用大顶堆要把所有元素进行排序，那能不能只排序k个元素呢？

所以用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素

  • 寻找前k个最大元素流程

image

class Solution {
private:
    class MyMinHeap{
    public:
        bool operator()(const pair<int,int>& lhs,const pair<int,int>& rhs){
            return lhs.second>rhs.second;
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //统计元素出现频率
        unordered_map<int,int>map;//map<nums[i]>对应出现的次数
        for(int i=0;i<nums.size();i++){//统计数组中每个数字出现次数
            map[nums[i]]++;//如果还没有，先自动插入键nums[i]并把值初始化为0，再返回引用，把该键对应的计数加1
        }
        
        //频率排序
        priority_queue<pair<int,int>,vector<pair<int,int>>,MyMinHeap>pri_que;//声明了一个以vector为底层容器、元素是（数字,频率）二元组、按频率升序的优先队列pri_que
        for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){//固定大小为k的小顶堆扫描所有频率的数值
            pri_que.push(*it);
            if(pri_que.size()>k){//堆大小小于k则队列弹出，保证堆大小一直为k
                pri_que.pop();
            }
        }
        
        //找出前k个高频元素（小顶堆先弹出的是最小的，所以倒序来输出到数组）
        vector<int> result(k);
        for(int i=k-1;i>=0;i--){
            result[i]=pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};
  • 时间复杂度：O(nlogk)
  • 空间复杂度：O(n)

总结

  • 栈里面的元素在内存中是连续分布的么？
  • 陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的
  • 陷阱2：缺省情况下，默认底层容器是deque，那么deque在内存中的数据分布是什么样的呢？

答案：不连续的

  • 递归为什么可以返回上一层位置？

递归的实现是栈：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数

 评论
评论插件加载失败
正在加载评论插件
  1. 栈与队列
    1. 基础知识
    2. 用栈实现队列
    3. 用队列实现栈
      1. 改进
    4. 有效的括号
    5. 删除字符串中的所有相邻重复项
      1. 改进
    6. 逆波兰表达式求值
    7. 滑动窗口最大值
      1. 单调队列
      2. 优先队列
    8. 前 K 个高频元素
      1. 优先队列
  2. 总结
  1. 栈与队列
    1. 基础知识
    2. 用栈实现队列
    3. 用队列实现栈
      1. 改进
    4. 有效的括号
    5. 删除字符串中的所有相邻重复项
      1. 改进
    6. 逆波兰表达式求值
    7. 滑动窗口最大值
      1. 单调队列
      2. 优先队列
    8. 前 K 个高频元素
      1. 优先队列
  2. 总结