【栈和队列高频考点题】(一)

简介: 【栈和队列高频考点题】(一)

1 与栈有关的考题

1.1 最小栈

题目描述:

8f751949183d4e6f850b29bb13795ff7.png 解题思路:

要想在O(1)时间内获得栈内最小元素只用一个栈肯定是行不通的,所以我们不妨再开一个栈来记录当前栈里面每个元素的最小值,这样就要多开出O(N)的空间,可以优化空间的方法是并不是所有的元素都要入最小栈,而是当前元素比最小栈栈顶的数据大便不必再入数据了,但是等于时一定要入进去,当pop掉元素时只需要比较普通栈与最小栈栈顶元素是否相等,若相等,则最小栈栈顶数据也得pop。

参考代码:

class MinStack {
public:
    MinStack() {}
    void push(int val) {
        _st.push(val);
        if(_minSt.empty() || _minSt.top()>=val)
            _minSt.push(val);
    }
    void pop() {
         if(_minSt.top()==_st.top())
            _minSt.pop();
         _st.pop();
    }
    int top() {
        return _st.top();
    }
    int getMin() {
        return _minSt.top();
    }
    stack<int> _st;
    stack<int> _minSt;//记录最小的数据
};

运行结果:

d8ee5956cf6546f18e69f5986446c072.png

题后反思:

万一数据像这种22222222,貌似我们优化空间的方法起不到作用了,可以采取的优化措施是我们存储数据时可以存一个pair,里面额外记录一下变量的个数,当有重复数据时便不再入数据了,而是++里面的计数器,pop时就--里面的计数器,大家有兴趣可以自己实现下,这里我就不再实现了。

1.2 栈的弹出压入序列

题目描述:

095bef7dc61d48df959b3380ec88709b.png

解题思路:

这道题的解决方法有很多种,这里分享一种比较容易理解的思路:另外搞一个栈,将栈的压入序列不断的push到这个栈中,当该栈不为空并且栈的弹出序列与该栈栈顶数据相等时就pop掉该栈栈顶数据,然后不断迭代走,最后返回值就是该栈是否为空或者是否走到了弹出序列的尾。

参考代码:

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> v;
        int pushi=0,popi=0;
        while(pushi<pushV.size())
        {
            v.push(pushV[pushi++]);
            while(!v.empty() && v.top()==popV[popi])
            {
                v.pop();
                popi++;
            }
        }
        return v.empty();
    }
};

运行结果:

8d1a71fda5aa4b4683aa3f767bb9cb5e.png

1.3 逆波兰表达式求值

题目描述:

337281658a084cd8b0b13551e47b5579.png

解题思路:

由于逆波兰表达式就是后缀表达式,运算符的优先级已经确定了,所以我们只需要模拟下运算的过程即可,注意先取的数据是右,后取的数据为左。

参考代码:

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

运行结果:

aa5bcea21fa74a0c8d6a703ed40d14b9.png

题后反思:

假如给的不是后缀表达式,而是中缀表达式,如何将中缀表达式转化为后缀表达式呢?

给定中缀表达式【1+2*(3-4)+5/6】,我们如何将其转化为后缀表达式?

基本规则是这样的:当遇到操作数的时候我们直接输出;遇到操作符当栈为空就直接入栈,栈若不为空就与栈顶数据相比,若优先级大于栈顶就将该操作符入栈(由于后面操作符优先级可能更大,所以先让其入栈),若优先级小于或者等于栈顶,就将栈顶数据pop掉然后输出,直到栈为空或者遇到优先级更小的操作符,然后继续迭代直到访问到所有元素。

但是这个规则只适用于没有()的转换中,例如【1+2*3-4】可以转化成【1 2 3 * + 4 -】

但是像上面的那个栗子【1+2*(3-4)+5/6】貌似就不适用了,处理方法有两种:

第一种是不入()到栈中,当发现出现了()时就认为()中的运算符优先级非常大,就让其入栈,其他规则与基本规则类似。

第二种是将()入栈,当出现(时就认为(的优先级非常低,(目的是让括号中运算符入栈),当出现)时同样认为)的优先级非常低,(目的是让括号中运算符出栈输出)

无论使用哪种规则,我们都能够很轻易的将上述中缀表达式转化为:

【1 2 3 4 - * + 5 6 / +】


Fox!
+关注
目录
打赏
0
0
0
0
2
分享
相关文章
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
72 0
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
54 1
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等