反爬链接
stack和queue都是容器适配器。

1. stack

<img src= " title="">
常用接口：
" title="">
stack的使用，因为先进后出，不支持迭代器 ——

#include<iostream>
#include<queue>

using namespace std;

void test_stack()
{
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);

    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
}

1.1 经典题目解题

1.1.1 最小栈

题目传送：155. 最小栈 - 力扣（LeetCode） (leetcode-cn.com)

要求：实现一个能在常数时间内检索到最小元素的栈。如果用一个min来遍历记录，显然不满足O(1)的时间复杂度。

于是我们再开一个_minST，以空间换时间， _st.push()时同时比较，把较小值也压入 _minST中，pop时 _st和 _minST同时弹栈，这样取 _minST栈顶元素即最小值 ——

<img src= " title="">
然而这样存储了了很多的重复数字，于是对于 _ minST, 我们可以只在< = 时入栈，_st的栈顶元素和 _minST相等再出栈 ——
" title="">
注意=时也要入栈！！

class MinStack {
public:
    MinStack() {
        //默认的即可：自定义类型自动调用它的构造函数
    }
    
    void push(int val) {
        _st.push(val);
        if(_minST.empty() || val <= _minST.top())
            // 出现<=前面的值，则插入新的最小数据
            _minST.push(val);
    }
    
    void pop() {
        if(_st.top() == _minST.top())
            _minST.pop();
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minST.top();
    }

private:
    stack<int> _st;
    stack<int> _minST;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

1.1.2 栈的弹出、压入序列

题目传送：栈的压入、弹出序列_牛客网 (nowcoder.com)

用入栈顺序来模拟出栈顺序。

扫描入栈序列，与出栈序列比对，对栈进行操作 ——

入栈位置和出栈位置不相等 → 入栈，后面再出
入栈位置和出栈位置相等 → 则证明该元素刚入即出（但是这个元素也要入栈，方便后序持续出数据）
- 持续出数据直至栈为空/栈顶元素和出栈序列的值不匹配

匹配条件：_st为空/出栈序列走到尾.

画图举例1 ——

例2 ——

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        int popi = 0;
        for(auto e : pushV)
        {
            st.push(e);
            //可能连续pop
            while(!st.empty() && st.top() == popV[popi]) 
            {
                st.pop();
                popi++;
            }
        }
        //return popi == popV.size();
        return st.empty();
    }
};

1.1.3 逆波兰表达式求值

题目传送：150. 逆波兰表达式求值 - 力扣（LeetCode） (leetcode-cn.com)

后缀表达式转化为中缀表达式计算。

操作数，入栈
操作符，连续取两个栈顶元素进行计算(先出的是右操作数，后出的的是左操作数)，运算结果继续入栈

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(const auto& s:tokens)
        {
            if(s == "+" || s == "-" || s == "*" || s == "/")
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                switch(s[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                    case '-':
                        st.push(left-right);
                        break;
                    case '*':
                        st.push(left*right);
                        break;
                    case '/':
                        st.push(left/right);
                        break;
                }
            }
            else
            {
                st.push(stoi(s));
            }
        }
        return st.top();
    }
};

众所周知，对于计算机而言，中缀表达式有优先级问题，而后缀表达式操作符都按优先级排列好了，如何将中缀表达式转化为后缀表达式呢？

遇到操作数，输出/存起来

遇到操作符

- 栈为空，直接入栈

- 栈不为空，跟栈顶的操作符比较

       - 若优先级更高，不能运算，因为可能有更高的 → 入栈
   - 若优先级低/相等 → 此时栈顶的操作符出栈，表示此时可以进行运算。

该运算符还需要继续跟栈顶元素进行比较，直至栈为空/比栈顶元素优先级高 →该操作符入栈

1.1.4 两个栈实现队列

题目传送：232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

过于经典的题目，在C数据结构题解写过了，那篇小文章浏览量竟然还在往上涨，震惊。

class MyQueue {
public:
    MyQueue() 
    {}
    
    void push(int x) {
        _pushST.push(x);
    }
    
    int pop() {
        if(_popST.empty())
        {
            while(!_pushST.empty())
            {
                _popST.push(_pushST.top());
                _pushST.pop();
            }
        }
        int top = _popST.top();
        _popST.pop();
        return top;
    }
    
    int peek() {
        if(_popST.empty())
        {
            while(!_pushST.empty())
            {
                _popST.push(_pushST.top());
                _pushST.pop();
            }
        }
        return _popST.top();
    }
    
    bool empty() {
        return _pushST.empty() && _popST.empty();
    }

    stack<int> _pushST;
    stack<int> _popST;
};

/**
 * 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();
 */

1.2 stack的模拟实现

stack和queue都是容器适配器。所谓适配器，是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计的经验总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

stack不再自己费劲儿实现一个容器，而是作容器适配器，对特定类进行封装。比如，stack以vector作为底层容器，就是一个数组栈；以list作为底层容器，就是一个链式栈。我们传入不同的模板参数(默认缺省给deque)来控制底层容器类型，这样就算底层千差万别，依然能够满足栈的性质。

并提供一组成员函数来访问栈元素，这要求底层容器类支持push_back、pop_back、back等接口，否则会报错。

:purple_heart: 模拟实现

#pragma once

#include<iostream>
#include<vector>
#include<list>
#include<forward_list>

using namespace std;

namespace beatles
{
    template<class T,class Container = deque<T>>
    class stack
    {
    public:
        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_back();
        }

        const T& top() const
        {
            return _con.back();
        }

        size_t size() const
        {
            return _com.size();
        }

        bool empty() const
        {
            return _con.empty();
        }
    private:
        Container _con;
    };

    void test_stack()
    {
        stack<int, vector<int>> st;
        //stack<int, list<int>> st;
        //stack<int, string> st; //报错：有截断问题
        //stack<int, forward_list<int>> st;//报错：单链表。不支持push_back、back
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);

        while (!st.empty())
        {
            cout << st.top() << " ";
            st.pop();
        }
        cout << endl;
    }
}

2. queque

<img src= " title="">
常用接口：
" title="">

使用 ——

#include<iostream>
#include<queue>

using namespace std;

void test_queue()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);

    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

2.1 两个队列实现栈

题目传送：225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)

过于经典的题目了，_q2完全用作辅助队列，出入数据都在 _q1。

class MyStack {
public:
    MyStack() 
    {}
    
    void push(int x) {
        _q1.push(x);
    }
    
    int pop() {
        while(_q1.size() >1)
        {
            _q2.push(_q1.front());
            _q1.pop();
        }
        int top = _q1.front();
        _q1.pop();
        
        //把_q2队列中的数据倒腾回_q1
        while(_q2.size())
        {
            _q1.push(_q2.front());
            _q2.pop();
        }
        return top;
    }
    
    int top() {
        return _q1.back();
    }

    bool empty() {
        return _q1.empty();
    }

    queue<int> _q1;
    queue<int> _q2;
};

/**
 * 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();
 */

2.2 queue的模拟实现

与stack一样，queue也是适配器。但是不能用vector作为底层容器类，因为vector的头删效率太低，没有提供pop_front接口。如果不给，缺省默认给deque，至于为什么后文详谈。

#pragma once

#include<iostream>
#include<deque>
using namespace std;

namespace beatles
{
    template<class T,class Container = deque<T>>
    class queue
    {
    public:
         size_t size() const
        {
            return _con.size();
        }

        bool empty() const
        {
            return _con.empty();
        }

        const T& back() const
        {
            return _con.back();
        }

        const T& front() const
        {
            return _con.front();
        }

        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_front();
        }
    private:
        Container _con;
    };

    void test_queue()
    {
        queue<int> q;
        //queue<int, list<int>> q;
        //queue<int, vector<int>> q; //报错：pop_front不是成员
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);

        while (!q.empty())
        {
            cout << q.front() << " ";
            q.pop();
        }
        cout << endl;
    }
}

3. deque: stack和queue的底层结构

众所周知，vector连续的物理空间带来了优点，它支持随机访问，CPU高速缓存命中率高，另外尾插尾删效率高；但也同时带来了缺点，不适合头插头删，另外扩容效率较低，也会造成一定的空间浪费。list按需申请释放空间，支持任意位置的 O(1) 插入删除；但不支持下标随机访问。

双端队列deque就是为了融合二者优点而产生的。

它支持随机迭代器、下标访问、任意位置的插入和删除 ——

可是它却是失败的。

3.1 deque原理

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下 ——
在这里插入图片描述

这样，与vector相比，deque头插头删不需要挪动数据，且扩容时的代价也大大降低；与list相比，deque高速缓存命中率高，且不需要频繁的申请释放空间，且可以“随机访问”。

但是随机，又没有完全随机(底层通过iterator复杂的设计)；且insert和erase也比较复杂。所以要高频随机访问还得是vector，要任意位置插入删除还得是list。它没能取代list和vector的宝座，但它很适合头尾的插入删除(双端)。

3.2 why？

:heart: 为什么选择deque作为stack和queue的底层默认容器？

实现stack ——

deque → vector 优势：扩容代价不大，不需要拷贝数据释放空间(中控数组满了需要扩容)；浪费空间不多
deque → list 优势：CPU高速cache命中率高；不会频繁申请释放小块空间。

实现queue ——

deque → list：同上，CPU高速cache命中率高；不会频繁申请释放小块空间。

实现stack和queue也刚好避开了deque的缺陷。

总之，deque作为stack和queue的默认容器是完胜的。

【C++】stack和queue的经典题目&模拟实现@STL

1. stack

1.1 经典题目解题

1.1.1 最小栈

1.1.2 栈的弹出、压入序列

1.1.3 逆波兰表达式求值

1.1.4 两个栈实现队列

1.2 stack的模拟实现

2. queque

2.1 两个队列实现栈

2.2 queue的模拟实现

3. deque: stack和queue的底层结构

3.1 deque原理

3.2 why？

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++】stack和queue的经典题目&模拟实现@STL

1. stack

1.1 经典题目解题

1.1.1 最小栈

1.1.2 栈的弹出、压入序列

1.1.3 逆波兰表达式求值

1.1.4 两个栈实现队列

1.2 stack的模拟实现

2. queque

2.1 两个队列实现栈

2.2 queue的模拟实现

3. deque: stack和queue的底层结构

3.1 deque原理

3.2 why？

热门文章

最新文章

相关课程

相关电子书