stack经典题

1.	最小栈	简单	跳转	LeetCode
2.	压入弹出序列	中等	跳转	牛客
3.	逆波兰式计算	中等	跳转	LeetCode
4.	用栈实现队列	简单	跳转	LeetCode

LeetCode 155：最小栈

这道题关键点在于要在常数时间内检索到一个栈中的最小元素，所以我们可以额外实现一个栈，这个栈的栈顶始终保存的是原栈的最小的元素，在插入和删除时都要进行判断

class MinStack { public:/** initialize your data structure here. */MinStack()//如果不写C++也会自动调用stack的默认构造函数{}void push(int val) {_elements.push(val);if(_min.empty() || val<=_min.top())//如果插入的元素要比最小栈的栈顶元素还要小，那么入栈_min.push(val);}void pop() {if(_min.top()==_elements.top())//最小栈保存的是元素栈中最小的元素，所以如果它被溢出了，那么最小栈也相应要被移除_min.pop();_elements.pop();}int top() {return _elements.top();}int getMin() {return _min.top();} private:stack<int> _elements;stack<int> _min; };/*** 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();*/

LeetCode 156：压入弹出序列

这道题比较经典，可以使用栈来模拟这个过程。如下，用pushi扫描pushv，用pushj扫描popv，如果s为空或s的栈顶元素和popv[popj]不相等，说明此时的进栈序列的这个元素不是立马出栈的，因此让其入栈，知道某一个s.top==popv[popj]时，就表明此时可以出栈了，一次类推。
如果最后popj走到了popv的末尾那肯定是满足的情况

class Solution { public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {if(pushV.size()!=popV.size()){return false;//长度不一致}stack<int> s;//用s这个栈进行模拟出栈size_t pushi=0;//用pushi去扫描pushVsize_t popj=0;//用popi去扫描popVwhile(popj<popV.size())//一旦不在while循环内return，那么肯定是满足情况的{while(s.empty() || s.top()!=popV[popj])//1：空是因为开始的时候栈是空的。2：如果s的栈顶元素不等于出栈序列的对应元素，表明，此时的栈顶元素不是立即出栈的，所以先入栈，待以后出栈{if(pushi>pushV.size())//这种情况就是不满足了，因为pushi已经跑到最后了return false;else{s.push(pushV[pushi]);//进栈pushi++;}}s.pop();//如果栈顶元素和出栈序列的栈顶元素相等，表明此时出栈序列的该元素应该要出栈了popj++; }return true;} };

LeetCode 150：逆波兰表达式求值

这个问题也是栈的经典问题，我在这篇文章专门讲到了这个专题

使用栈解决的一类经典问题：表达式转换及求值

LeetCode 232：用栈实现队列

用两个栈实现队列，s1用来入，s2用来接口操作，入“队列时”直接入s1，pop时如果s2不空那么就先出s2的，因为此时s2里面的是以前的元素，如果s2空了，那么就把s1的元素依次出栈然后入s2，然后再出栈
具体过程可以看这篇博客

数据结构-线性表之用队列实现栈&&用栈实现队列

class MyQueue { public:/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {s1.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {if(!s2.empty())//如果s2不空，那么先出s2{int temp=0;temp=s2.top();s2.pop();return temp;}while(!s1.empty())//如果s2空了，那么把s1的依次出栈，入栈到s2{int temp=s1.top();s2.push(temp);s1.pop();}int temp=0;temp=s2.top();s2.pop();return temp;}/** Get the front element. */int peek() {if(!s2.empty()){return s2.top();}while(!s1.empty()){int temp=s1.top();s2.push(temp);s1.pop();}return s2.top();}/** Returns whether the queue is empty. */bool empty() {return s1.empty() && s2.empty();}public:stack<int> s1;stack<int> s2; };

总结

以上是生活随笔为你收集整理的stack经典题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。