【C++】栈和队列的模拟实现 & 经典题目解析

发布于:2022-11-09 ⋅ 阅读:(12) ⋅ 点赞:(0) ⋅ 评论:(0)

🌈欢迎来到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的默认容器是完胜的,不能独挡一面,但是是一个好用的二把手(暗指谁哈哈哈)

📢写在最后

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

在这里插入图片描述