🌈欢迎来到C++专栏~~栈和队列经典题目 & 模拟实现

---

• (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort
• 目前状态：大三非科班啃C++中
• 🌍博客主页：张小姐的猫~江湖背景
• 快上车🚘，握好方向盘跟我有一起打天下嘞！
• 送给自己的一句鸡汤🤔：
• 🔥真正的大师永远怀着一颗学徒的心
• 作者水平很有限，如果发现错误，可在评论区指正，感谢🙏
• 🎉🎉欢迎持续关注！
  

一. Stack & Queue

常用成员函数：
简单使用一下栈，先进先出

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

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

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

💥经典题目

🥑最小栈

题目链接：155. 最小栈

🌍思路：

• 辅助栈，以空间换时间，st.push()时同时比较，把较小值也压入 minst中，pop时 st和 minST同时弹栈，这样取 minST栈顶元素即最小值 ——
• st尽管可能存储了很多相同的数据，但对于minst，我们只在< = 时入栈，st和 minST相同再一起出栈

class MinStack {
public:
    MinStack() {
        //默认的即可：自定义类型自动调用它的构造函数
    }
    
    void push(int val) {
        _st.push(val);

        if(_minst.empty() || val <= _minst.top())//顺序不能互换
            // 出现<=前面的值，则插入新的最小数据
            _minst.push(val);
    }
    
    void pop() {
        if(_minst.top() == _st.top())
            _minst.pop();//minst和st删除顺序不能换，先st删了，top数据就出错了
            
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }

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

🔥题目升级：如果插入大量重复数据（插入10w个1），怎么办？

• minst里面就存一个结构体，遇到相等就计数++

🥑栈的压入、弹出序列

题目链接：JZ31 栈的压入、弹出序列

🌍入栈顺序来模拟出栈顺序

首先对入栈序列进行遍历，对栈进行操作

• 入栈数据与出栈数据不相同 —>入栈
• 入栈数据与出栈数据相同 ——> 出栈，也就是刚进栈就出去了
• 不断重复，直到栈为空/栈顶元素和出栈序列的值不匹配就结束了

画图分析：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        int popi = 0;
        for(auto e:pushV)
        {
            st.push(e);
            //匹配后要持续比较，可能有多个匹配
            while(!st.empty() && st.top() == popV[popi])
            {
                st.pop();
                popi++;
            }
        }
        return st.empty();
    }
};

🥑逆波兰表达式求值

题目链接：150. 逆波兰表达式求值

后缀表达式转成中缀表达式
🌍思路：

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

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto& str : tokens)
        {
            if(str== "+" || str== "-" || str== "*" ||str== "/")
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();


                switch(str[0])//取str[0]就是char
                {
                    case '+':
                        st.push(left+right);
                        break;
                    case '-':
                        st.push(left-right);
                        break;
                    case '*':
                        st.push((long long)left*right);
                        break;
                    case '/':
                        st.push(left/right);
                        break;
                }
            }
            //操作数
            else
            {
                st.push(stoll(str));
            }
        }
        return st.top();
    }
};

吐槽:有一个奇葩的测试用例是 long long，最后还要转成int（无语）

🔥升级：对于计算机而言，中缀表达式有优先级问题，而后缀表达式操作符都按优先级排列好了，如何将中缀表达式转化为后缀表达式呢？（和上面恰恰相反）

• 遇到操作数，直接输出
• 操作符
  • 若栈为空，直接入栈
  • 栈不为空，跟栈顶的操作符比较（每次和前一个操作符比较）
    • 若优先级更高，不能运算，因为可能有更高的 → 入栈
    • 相反，优先级低/相等 → 此时栈顶的操作符出栈，表示此时可以进行运算

再升级：带（）的优先级：1 +（ 2 + 3 ）* 4 - 5

• 用flag代表括号，临时升高优先级

🥑两个栈实现队列

题目链接：232. 用栈实现队列

思路可参考：此文章——>【数据结构】栈实现队列 & 队列实现栈🥑

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();
    }
private:
    stack<int> pushst;
    stack<int> popst;
};

🥑两个队列实现栈

题目链接：225. 用队列实现栈

详细思路：详细看上面的链接,就是_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();

        //数据倒回给_q1
        while(_q2.size())
        {
            _q1.push(_q2.front());
            _q2.pop();
        }
        return top;

    } 
    
    int top() {
        return _q1.back();
    }
    
    bool empty() {
        return _q1.empty();
    }
private:
    queue<int> _q1;
    queue<int> _q2;
};

二. 容器适配器

🌈什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口，说白了就是：不是写死的，谁只要合适就可以来用

🌈STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

三. 栈和队列的模拟实现

💥stack的模拟实现

#pragma once
#include<deque>

namespace ljj
{ 
	//适配器
	template<class T, class Container = deque<T>>//deque后面细说
	class Stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

	    T& top()//使用通用的接口，不要用[]
		{
			return _con.back();
		}

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

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

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


	private:
		//封装一个容器vector
		//vector<T> _con; 不够灵活
		
		//只要Container满足上面的接口都可以
		Container _con;
	};
}

void test_stack()
{
	//底层大有不同，但是表面我们看不出来
	//ljj::Stack<int , vector<int>> st;
	//ljj::Stack<int , list<int>> st;

	ljj::Stack<int> st;//deque适配出来的

	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);

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

💥Queue的模拟实现

#pragma once
#include<deque>

namespace ljj
{
	//适配器
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

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

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

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


	private:
		Container _con;
	};
}

void test_queue()
{
	//ljj:queue<int> q;
	//不想用默认的deque可以用其他
	ljj:queue<int, list<int>> q;

	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);

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

四. deque: stack和queue的底层结构（了解）

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

而双端队列deque就是为了融合二者优点而产生的 ~ 比如詹姆斯（进攻防守都厉害）（有伏笔）

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

⚡底层原理

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高

🎨deque并不是真正连续的空间，而是由一段段连续的小空间buffer拼接而成的，其底层结构如下 ——

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

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示

那deque是如何借助其迭代器维护其假想连续的结构呢？

insert和erase也比较复杂。所以要高频随机访问还得是vector，要任意位置插入删除还得是list。它没能取代list和vector的宝座，但它很适合头尾的插入删除(双端)

⚡缺点

• operator[]计算稍显复杂，大量使用，性能下降（不如vector的[]）
• 中间插入删除效率不高（要么挪动数据，要么改buffer的空间，都不好）
• 底层角度迭代器很复杂

所以要高频随机访问还得是vector，要任意位置插入删除还得是list。它没能取代list和vector的宝座，但它很适合头尾的插入删除(双端)

⚡为什么

为什么选deque来作为stack和list的底层默认容器?

• stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
• 在stack中元素增长时，deque比vector的效率高；queue中的元素增长时，deque不仅效率高，而且内存使用率高。vector当容量不够时，会开更大的空间，拷数据然后释放原来的空间，操作复杂。而deque会找另一块内存继续存放数据，效率高。
• 相比较list，deque的插入操作会更加的高效，而且内存的使用率高，list会导致更多的内存碎片。

刚好都避开了deque的缺点
所以，deque作为stack和queue的默认容器是完胜的，不能独挡一面，但是是一个好用的二把手（暗指谁哈哈哈）

📢写在最后

笔试强训延迟了，微信还被封了一周，泪目