【ps】本篇有 5?道 leetcode OJ。

目錄

一、算法簡介

二、相關(guān)例題

1）刪除字符串中的所有相鄰重復項

.1- 題目解析

.2- 代碼編寫

2）比較含退格的字符串

.1- 題目解析

.2- 代碼編寫

3）基本計算器?II

.1- 題目解析

.2- 代碼編寫

4）字符串解碼

.1- 題目解析

.2- 代碼編寫

5）驗證棧序列

.1- 題目解析

.2- 代碼編寫

---

一、算法簡介

????????棧是一種特殊的線性表，只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底，棧中的數(shù)據(jù)元素遵守后進先出的原則。它的插入操作叫做進棧（或進棧/入棧），插入的數(shù)據(jù)在棧頂；刪除操作叫做出棧。出的數(shù)據(jù)也在棧頂。

? ? ? ? 棧一般與模擬算法結(jié)合在一起出題，在題目中野經(jīng)常充當數(shù)據(jù)的緩存容器，來幫助模擬入棧和出棧的過程以求得結(jié)果。

二、相關(guān)例題

1）刪除字符串中的所有相鄰重復項

1047. 刪除字符串中的所有相鄰重復項

.1- 題目解析

? ? ? ? 我們用一個新字符串，對每個字符模擬入棧和出棧的過程即可，具體方式是遍歷字符串，從左往右依此將字符入棧（尾插入新字符串），如果當前字符與棧頂?shù)淖址?#xff08;新字符串的末尾字符）相同，就將棧頂?shù)淖址鰲?#xff08;對新字符串尾刪），且跳過當前字符，繼續(xù)遍歷下一個字符。

.2- 代碼編寫

class Solution {
public:string removeDuplicates(string s) {string ret;for(int i=0;i<s.size();i++){//用一個新字符串對每個字符模擬入棧和出棧的過程if(ret.size() && s[i]==ret.back())ret.pop_back();else ret+=s[i];}return ret;}
};

2）比較含退格的字符串

844. 比較含退格的字符串

.1- 題目解析

? ? ? ? 類似的，這道題也可以用字符串來模擬入棧和出棧的過程，但與上道題不同的是，出棧的條件變成了若當前字符為 '#'，入棧的條件為若當前字符不為 '#'。

.2- 代碼編寫

class Solution {
public:bool backspaceCompare(string s, string t) {return stackString(s)==stackString(t);}//用一個新字符串模擬入棧和出棧的過程string stackString(string& s){string st;for(auto ch:s){if(ch=='#'){if(st.size())st.pop_back();}else {st+=ch;}}return st;}
};

3）基本計算器?II

227. 基本計算器 II

.1- 題目解析

????????這道題只有加減乘除四個運算，沒有括號，并且每一個數(shù)都是大于等于 0 的，?這樣可以大大地減少需要處理的情況。

????????由于表達式里面沒有括號，因此只用處理加減乘除混合運算即可，這樣不需要用到雙棧。根據(jù)四則運算的順序，我們可以先計算乘除法，然后再計算加減法。由此可以得出下面的結(jié)論：

• 當一個數(shù)前面是 ' + ' 號的時候，這?個數(shù)是否會被立即計算是不確定的，因此可以先入棧。
• 當一個數(shù)前面是 ' - ' 號的時候，這?個數(shù)是否被立即計算也是不確定的，但是這個數(shù)已經(jīng)和前面的負號綁定了，因此可以將這個數(shù)的相反數(shù)入棧。
• 當一個數(shù)前面是 ' * ' 號的時候，這?個數(shù)可以立即與前面的?個數(shù)相乘，此時讓將棧頂?shù)脑爻松线@個數(shù)；
• 當一個數(shù)前面是 ' / ' 號的時候，這?個數(shù)也是可以立即被計算的，因此讓棧頂元素除以這個數(shù)。

????????當遍歷完完整的表達式時，棧中剩余的元素之和就是最終結(jié)果。此外，這里可以用數(shù)組來模擬棧。

.2- 代碼編寫

class Solution {
public:int calculate(string s) {char op='+';//表達式開頭沒有運算符，但應(yīng)默認是+號int i=0,n=s.size();vector<int> st;//用數(shù)組模擬棧while(i<n){if(s[i]==' ')i++;//跳過空格else if(s[i]>='0'&&s[i]<='9'){int tmp=0;//提取一個完整的操作數(shù)while(i<n && s[i]>='0'&& s[i]<='9'){tmp=tmp*10+(s[i++]-'0');}//按運算符處理操作數(shù)if(op=='+')st.push_back(tmp);else if(op=='-')st.push_back(-tmp);else if(op=='*')st.back()*=tmp;else if(op=='/')st.back()/=tmp;}else op=s[i++];}//累加棧中的數(shù)，即可得到結(jié)果int ret=0;for(auto x:st)ret+=x;return ret;}
};

4）字符串解碼

394. 字符串解碼

.1- 題目解析

? ? ? ? 本題可以用兩個棧來模擬解碼的過程，其中一個棧存字符，另一個棧存數(shù)字。

? ? ? ? 解碼的順序，是從括號內(nèi)部向外部依此解碼，如：3[ab2[cd]] -> 3[abcd cd] -> abcdcd abcdcd abcdcd 。

.2- 代碼編寫

class Solution {
public:string decodeString(string s) {stack<int> nums; //數(shù)字棧stack<string> st;//字符棧st.push("");//預(yù)留一個空字符串，以防越界訪問int i=0,n=s.size();while(i<n){//提取數(shù)字放入數(shù)字棧中if(s[i]>='0'&&s[i]<='9'){int tmp=0;while(s[i]>='0'&&s[i]<='9'){tmp=tmp*10+(s[i++]-'0');}nums.push(tmp);}//遇到'['，提取字符串放入字符棧中else if(s[i]=='['){i++;string tmp;while(s[i]>='a'&&s[i]<='z'){tmp+=s[i++];}st.push(tmp);}//遇到']'，解析，然后將其尾插到字符棧棧頂字符串的后面else if(s[i]==']'){string tmp=st.top();st.pop();int k=nums.top();nums.pop();while(k--){st.top()+=tmp;}i++;}//提取字符串，直接尾插到字符棧棧頂字符串的后面else{string tmp;while(i<n && s[i]>='a'&& s[i]<='z'){tmp+=s[i++];}st.top()+=tmp;}}return st.top();}
};

5）驗證棧序列

946. 驗證棧序列

.1- 題目解析

? ? ? ? 這是一道經(jīng)典的棧相關(guān)的題目，給定一個進棧序列，再給定一個出棧序列，要求根據(jù)進棧序列判斷出棧序列是否合法。

? ? ? ? 我們可以創(chuàng)建一個棧，然后分別遍歷這兩個序列，來模擬進棧和出棧的過程。遍歷進棧序列的時候，先將序列中的元素依此 push 入棧，再遍歷出棧序列中的元素，如果當前元素與剛?cè)霔５倪@個元素相同，那么就將其出棧，如果不是，就繼續(xù)對進棧序列中的元素進行入棧，直到遇到出棧序列中的相同元素再出棧。如此，遍歷完兩個序列后，如果棧為空，則說明棧序列是合法的。

.2- 代碼編寫

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int i=0;for(auto x:pushed){st.push(x);while(st.size()&&st.top()==popped[i]){st.pop();i++;}}return st.empty();}
};