1.	最小棧	簡單	跳轉	LeetCode
2.	壓入彈出序列	中等	跳轉	牛客
3.	逆波蘭式計算	中等	跳轉	LeetCode
4.	用棧實現(xiàn)隊列	簡單	跳轉	LeetCode

LeetCode 155：最小棧

這道題關鍵點在于要在常數(shù)時間內(nèi)檢索到一個棧中的最小元素，所以我們可以額外實現(xiàn)一個棧，這個棧的棧頂始終保存的是原棧的最小的元素，在插入和刪除時都要進行判斷

class MinStack { public:/** initialize your data structure here. */MinStack()//如果不寫C++也會自動調(diào)用stack的默認構造函數(shù){}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：壓入彈出序列

這道題比較經(jīng)典，可以使用棧來模擬這個過程。如下，用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循環(huán)內(nèi)return，那么肯定是滿足情況的{while(s.empty() || s.top()!=popV[popj])//1：空是因為開始的時候棧是空的。2：如果s的棧頂元素不等于出棧序列的對應元素，表明，此時的棧頂元素不是立即出棧的，所以先入棧，待以后出棧{if(pushi>pushV.size())//這種情況就是不滿足了，因為pushi已經(jīng)跑到最后了return false;else{s.push(pushV[pushi]);//進棧pushi++;}}s.pop();//如果棧頂元素和出棧序列的棧頂元素相等，表明此時出棧序列的該元素應該要出棧了popj++; }return true;} };

LeetCode 150：逆波蘭表達式求值

這個問題也是棧的經(jīng)典問題，我在這篇文章專門講到了這個專題

使用棧解決的一類經(jīng)典問題：表達式轉換及求值

LeetCode 232：用棧實現(xiàn)隊列

用兩個棧實現(xiàn)隊列，s1用來入，s2用來接口操作，入“隊列時”直接入s1，pop時如果s2不空那么就先出s2的，因為此時s2里面的是以前的元素，如果s2空了，那么就把s1的元素依次出棧然后入s2，然后再出棧
具體過程可以看這篇博客

數(shù)據(jù)結構-線性表之用隊列實現(xiàn)棧&&用棧實現(xiàn)隊列

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经典题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。