目錄
關于棧的題目：
1. 最小棧：
?思路：
實現代碼(最終)：?
2. 棧的壓入、彈出序列：
思路：
實現代碼：
?3. 逆波蘭表達式求值：
思路：
實現代碼：
深入了解逆波蘭表達式：?
實現代碼：?
用棧實現隊列?
思路：?
實現代碼：
學了棧卻不知道該怎么用于做題？本篇將分享幾道棧相關的經典題目
關于棧的題目：
1. 最小棧：
?思路：
先拿示例一舉例，我們可以定義兩個棧，st和min
st用來存push進去的數據，而min用來存當前st中數據的最小值，具體怎么實現呢？模擬一下示例1
?實現代碼：
class MinStack {
public:/** initialize your data structure here. */MinStack() {//這里可以不用寫，會調用默認的構造函數}void push(int x) {st.push(x);//先入普通的棧if(min.empty() || x<min.top())//如果這個數據小于等于最小棧中棧頂的數據，就插入，讓x成為新的最小值min.push(x);}void pop() {if(st.top() == min.top())//如果要刪除的數和最小棧的棧頂的值相同，就代表要刪除的這個數也是現在棧中最小的數，所以要把最小棧中的那個數也pop掉min.pop();st.pop();}int top() {return st.top();//取普通棧的棧頂}int getMin() {return min.top();//取最小棧的棧頂}
private:stack<int> st;//普通用來存數據的棧stack<int> min;//用來存每一時期的最小值(棧頂就是當前時期的最小值)
};但如果運行的話會報錯
那我們就用這組出錯的數據再模擬一下
所以在第三步時(即插入第二個0)也應將0入棧min?
這樣即使再getmin，值也還會是0
實現代碼(最終)：?
class MinStack {
public:/** initialize your data structure here. */MinStack() {//這里可以不用寫，會調用默認的構造函數}void push(int x) {st.push(x);//先入普通的棧if(min.empty() || x<min.top())//如果這個數據小于等于最小棧中棧頂的數據，就插入，讓x成為新的最小值min.push(x);}void pop() {if(st.top() == min.top())//如果要刪除的數和最小棧的棧頂的值相同，就代表要刪除的這個數也是現在棧中最小的數，所以要把最小棧中的那個數也pop掉min.pop();st.pop();}int top() {return st.top();//取普通棧的棧頂}int getMin() {return min.top();//取最小棧的棧頂}
private:stack<int> st;//普通用來存數據的棧stack<int> min;//用來存每一時期的最小值(棧頂就是當前時期的最小值)
};2. 棧的壓入、彈出序列：
思路：
?先定義一個棧，用來模擬入棧出棧
?到下一次入棧時，此時st.pop() == pop[i]，所以就要開始出棧，直到st.pop() != pop[i]為止
出棧4后，現在的數據是這樣?
所以要繼續入棧
?刪除完最后一個數據之后
實現代碼：
bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
{stack<int> st;//創建一個棧，用來存pushV的數據int popi = 0;//popV的進度for(int i=0;i<pushV.size();i++)//每次都入棧pushV的數據{st.push(pushV[i]);while(!st.empty() && st.top() == popV[popi])//如果現在棧頂的數據等于popV進度的數據，就表示需要開始出棧了{st.pop();popi++;}}return st.empty();//如果最后棧里沒有數據了，就代表全pop完了，就是對的
}?3. 逆波蘭表達式求值：
思路：
逆波蘭表達式，也叫后綴表達式，我們平常用的表達式是中綴表達式，例如a+b,寫成后綴表達式就是ab+，即把操作符放到了數的后面，這是為了優先級的區分(更便于計算)，優先級越高的操作符就會越在前面
(a+b)*c-(a+b)/e轉換成后綴表達式就是ab+c*ab+e/-，即先讓"a"和"b"執行"+"操作，然后讓"a+b"的值和"c"執行"*"操作，再讓"a"和"b"執行"+"操作，以此類推
?相信對棧有一定了解的人都已經想到了，這道題可以用棧模擬的方法輕松解決
遇到非操作符就入棧，遇到操作符就把棧的前兩個元素出棧并運算，運算完把結果再入棧就可以
?具體點來說，拿示例1模擬
示例二模擬：
?
可以看到，最后存在棧(棧頂)的數據就是最終結果
實現代碼：
int evalRPN(vector<string>& tokens)
{stack<int> st;//用一個棧來模擬數運算的先后順序int i=0;while(i < tokens.size())//遍歷數組{if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/")//如果不是算數符就入棧st.push(stoi(tokens[i]));else//遇到算數符，就把棧的前兩個元素提出來(第一個提出來的是右元素，第二個是左元素){int right = st.top();st.pop();int left = st.top();st.pop();switch(tokens[i][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;}}i++;}return st.top();
}深入了解逆波蘭表達式：?
注：面試時一般不會考的這么深入，如果有興趣可以看看這部分內容
本題中給出的輸入就已經是逆波蘭表達式了，那中綴表達式是如何轉換成逆波蘭表達式(后綴表達式)的呢
例如，我們有一個中綴表達式1+2*4+3，根據優先級，它會先算2*4，再拿2*4的結果去算另外兩個加式，但如果直接這樣計算的話，不避免的會先算加法式，所以要給它轉換成后綴表達式后用棧的特性來計算
轉換成后綴表達式也需要用棧，下面來模擬一下過程
規則：
- 遇到數字，提出來(尾插到后綴表達式中)
- 遇到操作符，若此時棧為空，就入棧
- 遇到操作符，若此時棧不為空，如果當前操作符比棧頂的操作符優先級要高，就入棧
- 遇到操作符，若此時棧不為空，如果當前操作符比棧頂的操作符優先級要低或相等，就出棧掉相等的操作符(直到棧頂為空或比棧頂的優先級要低)，并將出棧的操作符尾插到后綴表達式中，然后再入棧新操作符
實現代碼：?
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;bool op(string s)//判斷是否為操作符
{if(s=="+"||s=="-"||s=="*"||s=="/")return true;elsereturn false;
}int priority(string s)//返回該操作符的優先級比
{if(s == "+" || s == "-")return 1;else return 2;
}
int main()
{vector<string> infix = {"1","+","2","*","4","+","3"};//待轉換的中綴表達式vector<string> postfix;//待尾插的后綴表達式stack<string> st;//存操作符的棧for(int i=0;i<infix.size();i++){if(op(infix[i]))//如果該位置是操作符{if(st.empty() || priority(st.top()) < priority(infix[i]))//如果棧為空或者棧頂的優先級比當前操作符低，則直接入棧{st.push(infix[i]);}else//否則棧頂的優先級比當前操作符高或相等，則將棧頂的操作符彈出，直到棧頂的優先級比當前操作符低，然后將當前操作符入棧{while(!st.empty() && priority(st.top()) >= priority(infix[i])){string s = st.top();st.pop();postfix.push_back(s);}st.push(infix[i]);}}else//如果該位置是操作數，則直接尾插到后綴表達式中{postfix.push_back(infix[i]);}}while(!st.empty())//將棧中剩余的操作符彈出并尾插到后綴表達式中{string s = st.top();st.pop();postfix.push_back(s);}for(const auto& s : postfix){cout << s << " ";}return 0;
}輸出結果：
用棧實現隊列?
思路：?
?眾所周知，棧是后進先出(LIFO)，而隊列是先進先出(FIFO)，想用兩個棧實現先進先出，可以用一個棧專門入數據，另外一個棧專門出數據
拿這個數據來舉例，現在我們要出隊的話，會先出1，怎么樣才能先讀到1呢？
再把數據全部都入到另外一個棧上，此時出棧的順序就和出隊一樣了
當然，還有很多細節沒有處理
只要要出棧時才會用到popst，所以只有要出棧時，才需要把pushst中的數據都入到popst中
并且，當popst中有數據時，就先不用把pushst中的數據入到popst，因為此時如果再入的話popst棧頂的數據就不是先進的那個數了
實現代碼：
class MyQueue {
public:MyQueue() {//讓它調用默認的構造函數就行(stack的構造函數)}void push(int x) {//往pushst中插入數據pushst.push(x);}//先在pushst中插入數據，這樣再一個個出棧到popst時，再popst.top()就是隊尾的數據了int pop() {if(popst.empty())//如果此時popst還是空的，就得先給popst數據{while(!pushst.empty()){int tmp = pushst.top();pushst.pop();popst.push(tmp);}}int x = popst.top();popst.pop();return x;}int peek() {if(popst.empty())//如果此時popst中沒有數據，就要先把pushst的數據給popst{while(!pushst.empty()){int tmp = pushst.top();pushst.pop();popst.push(tmp);}}return popst.top();}bool empty() {//只有兩個棧里都沒有數據才是真沒數據return pushst.empty() && popst.empty();}
private:stack<int> pushst;//負責入棧stack<int> popst;//負責出棧
};
)
