【刷题记录】stack queue的题目练习

这篇具有很好参考价值的文章主要介绍了【刷题记录】stack queue的题目练习。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 最小栈

题目链接:155. 最小栈 - 力扣(LeetCode)

题干:

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例:

输入:
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

题目分析:

为了能够在O(1)的时间复杂度内找到当前栈中的最小值,我们能想到使用两个栈,一个栈正常存储数据(数据栈),另一个栈存储当前栈中的最小值(最小栈),这样最小值就能直接找到。

每次push数据的时候数据站正常push,最小栈判断在push之前的最小值与当前值的大小,如果push数据小于最小栈的top,那么最小栈就push当前值,否则就push栈顶值。

【刷题记录】stack queue的题目练习

实际上,如果入栈的数据大多数都大于当前最小值时,最小栈中就会出现很多相同且连续的数,这样对于空间是很大的浪费,所以,我们可以考虑修改最小栈的入栈规则,只有当新入栈的数据小于当前最小值时才入最小栈,这样最小栈中的数据就不会出现这种冗余。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4feFqUnf-1682496626758)(null)]

代码实现:

//解法一:
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();
    }
    
    stack<int> _st;
    stack<int> _minst;
};

【刷题记录】stack queue的题目练习

2. 逆波兰表达式

题目链接:150. 逆波兰表达式求值 - 力扣(LeetCode)

题干:

给你一个字符串数组 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
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

题目分析:

对于逆波兰表达式的计算,我们按照顺序遍历的方式,找到第一个运算符,然后将前面两个操作数拿出来运算即可,按照这种方式,我们可以想到用栈来存放数据,遇到操作符就pop出两个元素用于运算

【刷题记录】stack queue的题目练习

代码实现:

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])//判断是什么运算,然后将运算结果入栈
                {
                    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(str));
            }
        }
        return st.top();
    }
};

【刷题记录】stack queue的题目练习

拓展知识:中缀表达式和后缀表达式

表达式时由操作数和操作符组成的,我们一般见到的表达式通常是把操作符放在两个操作数之间的,这种把操作符放在中间的表达式叫做中缀表达式,这种表达式对人类很友好,但是对计算机不太友好。波兰数学家Jan Lukasiewicz提出了另一种数学表示法,它有两种表示形式:把运算符写在操作数之前,称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression),如+AB;把运算符写在操作数之后,称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression),如AB+。在上题中提到的逆波兰表达式就是后缀表达式

这里给出中缀转后缀的算法思路:

  1. 创建栈
  2. 从左向右顺序获取中缀表达式
    • 数字直接输出
    • 运算符
      • 情况一:遇到左括号直接入栈,遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出,同时左括号出栈但是不输出。
      • 情况二:遇到乘号和除号直接入栈,直到遇到优先级比它更低的运算符,依次弹栈。
      • 情况三:遇到加号和减号,如果此时栈空,则直接入栈,否则,将栈中优先级高的运算符依次弹栈(注意:加号和减号属于同一个优先级,所以也依次弹栈)直到栈空或则遇到左括号为止,停止弹栈。(因为左括号要匹配右括号时才弹出)。
      • 情况四:获取完后,将栈中剩余的运算符号依次弹栈输出

3. 栈的压入弹出序列

题目链接:栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

题干:

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

  1. 0<=pushV.length == popV.length <=1000
  2. -1000<=pushV[i]<=1000
  3. pushV 的所有数字均不相同

示例1

输入:[1,2,3,4,5],[4,5,3,2,1]

返回值:true

解释:可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列,返回true

示例2

输入:[1,2,3,4,5],[4,3,5,1,2]

返回值:false

解释:由于是[1,2,3,4,5]的压入顺序,[4,3,5,1,2]的弹出顺序,要求4,3,5必须在1,2前压入,且1,2不能弹出,但是这样压入的顺序,1又不能在2之前弹出,所以无法形成的,返回false

题目分析:

对于这种题目,我们要想暴力穷举的话,那复杂度确实有点过于高了,所以现在有个想法就是能不能模拟一下栈的操作,并且与弹出序列对比

首先创建一个栈,然后遍历pushV中的数据,并压栈,然后判断栈顶的数据与popV中的当前数据是否相等,如果相等就出栈,否则就继续入栈,如果遍历完pushV之后,栈是空的,那么说明popV序列是可得的,返回true,否则返回false。

代码实现:

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

【刷题记录】stack queue的题目练习

4. 栈实现队列

题目链接:232. 用栈实现队列 - 力扣(LeetCode)

题干:

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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

题目分析:

按照题目要求,使用两个栈来实现一个队列。栈和队列都是容器适配器,只是提供的适配接口不同而已,栈是LIFO,队列是FIFO,所以我们使用两个栈来实现队列只需要控制好进队列和出队列的方式即可。

这里使用两个栈,我们分别命名为st_push,st_pop,对于进队列的操作,我们就把值push到st_push栈中出队列的操作我们就只出st_pop栈中的元素,然后在合适的时机将st_push栈中的元素转换到st_pop栈中。这里注意一下,每次转换的时候都一定要将push栈中所有元素转换到pop栈中,并且当pop栈为空时才能转换,否则数据顺序就乱了

【刷题记录】stack queue的题目练习

代码实现:

class MyQueue {
public:
    MyQueue() {//这里默认构造函数就不用实现了,因为在这里成员变量会走初始化列表,在初始化列表这里会自动调用成员变量类型的默认构造函数

    }
    void push(int x) {
        st_push.push(x);
    }    
    void conversion()//st_push ==> st_pop
    {
        if(st_pop.empty())
        {
            while(!st_push.empty())
            {
                st_pop.push(st_push.top());
                st_push.pop();
            }
        }
    }
    int pop() {
        conversion();//当pop栈为空时,从push栈中导入所有元素
        int ret = st_pop.top();
        st_pop.pop();
        return ret;
    }    
    int peek() {
        conversion();
        return st_pop.top();
    }  
    bool empty() {
        return st_pop.empty() && st_push.empty();
    }
    
    stack<int> st_push;
    stack<int> st_pop;
};

【刷题记录】stack queue的题目练习

5. 队列实现栈

题目链接:225. 用队列实现栈 - 力扣(LeetCode)

题干:

请你仅使用两个队列实现一个后入先出(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

题目分析:

和上一道题相同,我们只需要控制入栈和出栈的顺序即可

由于想出栈就得出队尾的元素,所以需要先把队列中其他元素都出了,才能出到队尾的元素,这时候出的元素就用另一个队列存放,入队列的顺序也是固定的,所以队列内元素的顺序还是不变的,所以再插入元素的时候在非空队列内继续插入即可

【刷题记录】stack queue的题目练习

代码实现:

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    MyStack() {//这里默认构造函数就不用实现了,因为在这里成员变量会走初始化列表,在初始化列表这里会自动调用成员变量类型的默认构造函数

    }
    void push(int x) {//这里在结构上保证必须有一个队列是空的
        if (q1.empty())
            q2.push(x);
        else
            q1.push(x);
    }
    int pop() {//在需要pop的时候将非空队列的前n个值转换到空队列中,然后pop非空队列
        if (q2.empty())
        {
            swap(q1, q2);
        }
        //此时q1为空,q2有值
        int size = q2.size();
        for (size_t i = 0; i < size - 1; ++i)
        {
            q1.push(q2.front());
            q2.pop();
        }
        int ret = q2.front();
        q2.pop();
        return ret;
    }
    int top() {//非空队列中的最后一个元素即是栈顶元素
        if (q1.empty())
        {
            return q2.back();
        }
        else
            return q1.back();
    }
    bool empty() {
        return q1.empty() && q2.empty();
    }
};

【刷题记录】stack queue的题目练习文章来源地址https://www.toymoban.com/news/detail-429585.html

到了这里,关于【刷题记录】stack queue的题目练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • stack和queue

    💓博主个人主页:不是笨小孩👀 ⏩专栏分类:数据结构与算法👀 C++👀 刷题专栏👀 C语言👀 🚚代码仓库:笨小孩的代码库👀 ⏩社区:不是笨小孩👀 🌹欢迎大家三连关注,一起学习,一起进步!!💓 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经

    2024年02月08日
    浏览(34)
  • 08.Stack和Queue

    栈:先进后出 队列:先进先出  JVM的栈就是平常所说的一块内存。 此处所说的栈是数据结构  栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In

    2024年02月06日
    浏览(32)
  • 【C++】stack & queue

    适配器 是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成我们希望的另外一个接口。 虽然 stack 和 queue 中也可以存放元素,但在 STL 中并没有将其划分在容器的行列,而是将其称为 容器

    2024年02月07日
    浏览(37)
  • stack_queue | priority_queue | 仿函数

    栈不在是一个容器,而是一个容器适配器 , stack的模板中第二个deque暂时不知道干什么的,后面会说 说明stack是一个容器适配器,并且为了保证严格的先进后出,所以不存在迭代器 这里假设我们不认识 deque,那么如果stack频繁使用pop尾删,将vector T 设置成缺省值也是非常适合

    2024年01月16日
    浏览(37)
  • STL——stack和queue

    stl中提供了栈和队列配接器供我们使用,以后就可以直接使用了。不需要我们自己造轮子。 使用细节参考文档就可以,与之学过的容器并无二致。栈和队列的特性我们再学习数据结构时已经了解了。这里就不在赘述了。 stack - C++ Reference (cplusplus.com) queue - C++ Reference (cplusplus

    2024年02月12日
    浏览(38)
  • 【C++ 】stack 和 queue

    stack 的介绍: 1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行 元素的插入与提取操作 2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定

    2024年04月15日
    浏览(28)
  • stack&queue的模拟实现

    stack模拟: stack的源代码: stack的全部源代码就这些。 stack的代码少,原因在于采用了适配器模式,所谓适配器,以电器为例,每个电器都有电源适配器,中国的家用电源为220V的交流电,但是几乎没有电器需要220V的交流电,所以每个电器都有一个电源适配器,将家庭电压转换

    2024年02月06日
    浏览(39)
  • 浅谈deque,queue,stack

    deque 和 queue 都是常用于存储元素的容器,但它们在数据结构和应用场景上有一些区别。 queue 是队列的一种实现,它只能从队首插入元素,而只能从队尾获取并移除元素。即,queue 满足 FIFO(先进先出)的特性。queue 通常用于实现任务队列、消息队列等场景。 deque 则是双端队

    2024年02月07日
    浏览(38)
  • [自我记录]随想录刷题第二天 | 977.有序数组的平方,209.长度最小的子数组,59.螺旋矩阵II

     代码随想录打卡第二天, 新手自我记录一下刷题历程, 仅为自我打卡使用. 今天刷了三道主题, 第一道双指针和第三道模拟做出来了, 第二道写出了暴力解法但是提交leetcode超时了, 测试用例过了18/20, 看了carl哥答案以后自己重新补写了滑动窗口方法. 977. 有序数组的平方 简单题

    2024年02月05日
    浏览(43)
  • C++ STL stack & queue

    目录 一.stack 介绍  二.stack 使用 三.stack 模拟实现 普通版本: 适配器版本: 四.queue的介绍 五. queue使用 六.queue模拟实现 七.deque介绍 1.容器适配器 2.deque的简单介绍 3.deque的缺陷 4.为什么选择deque作为stack和queue的底层默认容器 stack------reference 1. stack是一种容器适配器,专门用在

    2024年02月12日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包