算法訓練之棧

???~~~~~~歡迎光臨知星小度博客空間~~~~~~???

???零星地變得優秀~也能拼湊出星河~???

???我們一起努力成為更好的自己~???

???如果這一篇博客對你有幫助~別忘了點贊分享哦~???

???如果有什么問題可以評論區留言或者私信我哦~???
??????個人主頁??????

? ? ? ? 這一篇博客我們來探討一下有關于棧的算法練習題，準備好了嗎~我們發車去探索算法的奧秘啦~🚗🚗🚗🚗🚗🚗

前言😁

刪除字符串中所有相鄰重復項🙃

比較含退格的字符串😜

基本計算器Ⅱ😀

字符串解碼😍

驗證棧序列😝

前言😁

? ? ? ? 我們先來簡單復習一下棧這個數據結構，棧（Stack）是一種后進先出的數據結構，我們可以想象一疊盤子：你通常會把新洗好的盤子放在最上面（入棧），而當你需要用一個盤子時，你會從最上面拿走一個（出棧），你無法直接從中間或底部抽出一個盤子，棧的工作原理正是如此。

? ? ? ? 話不多說，我們上題~

刪除字符串中所有相鄰重復項🙃

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

? ? ? ? 看這題目有點眼熟，既然要刪除重復字符，我們就得記錄前面一個字符判斷是否重復，這也就使用到我們強大的數據結構——棧。

算法思路：棧模擬過程

①創建一個空棧

②遍歷字符串，如果棧不為空并且棧頂元素與當前字符相等，那么棧頂元素出棧；否則，當前字符入棧

③棧中剩余字符出棧保存到字符串中

代碼實現：

//刪除字符串中所有相鄰重復項
class Solution
{
public:string removeDuplicates(string s){//使用數據結構容器——棧stack<char> st;//遍歷字符串for (auto& e : s){//如果棧不為空并且棧頂元素與當前字符相等，那么棧頂元素出棧if (st.size() && e == st.top()){st.pop();}//否則，當前字符入棧(包括空棧的情況)else{st.push(e);}}string ret;//保存返回結果while (!st.empty()){ret += st.top();st.pop();}//逆序字符串就是正確結果reverse(ret.begin(), ret.end());return ret;}
};

順利通過~不過這里的代碼看起來還是有一些繁瑣，我們有沒有什么辦法優化一下，主要在于棧中保存的僅僅是字符，需要進行提取才能得到我們的答案，那我們可以與字符串聯系起來~

優化思路：因為要返回的是字符串，我們可以使用字符串來模擬棧工作的過程，字符串最后一個位置也就是我們的棧頂~

代碼實現：

class Solution
{
public:string removeDuplicates(string s){//字符串模擬棧string st;for (auto& e : s){if (st.size() && st.back() == e){st.pop_back();}else{st += e;}}return st;}
};

順利通過~

比較含退格的字符串😜

比較含退格的字符串

? ? ? ? 這一個題目與第一個題目類似，都是使用棧模擬這個過程，我們這里直接給出優化的算法思路~

算法思路：字符串模擬棧實現過程

①根據題目要求，每一個字符串進行相同的變化（封裝成一個函數changeS）

②changS函數內部使用字符串模擬棧，當棧不為空并且當前字符為‘#'時，棧頂元素出棧；否則，當前字符不為’#‘就入棧（如果對空文本輸入退格字符，文本繼續為空）

③判斷兩個字符串變化后是否相等

代碼實現：

//比較含退格的字符
class Solution
{
public:bool backspaceCompare(string s, string t){return changeS(s) == changeS(t);}string changeS(string s){string ret;for (auto& e : s){//當棧不為空并且當前字符為‘#'時，棧頂元素出棧if (ret.size() && e == '#'){ret.pop_back();}else if (e != '#')//小寫字母入棧{ret.push_back(e);}}return ret;}
};

順利通過~

基本計算器Ⅱ😀

基本計算器Ⅱ

? ? ? ? 題目要求我們實現一個簡單的計算器，我們這里給出一個巧妙的算法思路~

算法思路：使用棧保存正數或者負數

①棧存儲中間結果：棧用于存儲需要累加的值（正數或負數），乘除運算立即計算并更新棧頂

②運算符延遲處理：遇到新運算符時只記錄，遇到下一個數字時才應用上一個運算符

③處理優先級：通過立即計算乘除運算實現"先乘除后加減"

④空格直接跳過

⑤棧中所有數據相加就是計算結果

運算符處理規則

前一個運算符	當前數字處理方式
`+`	`st.push(val)`
`-`	`st.push(-val)`
`*`	`st.top() *= val`
`/`	`st.top() /= val`

代碼實現：

//基本計算器Ⅱ
class Solution
{
public:int calculate(string s){int n = s.size();char c = '+';//運算符號記錄stack<int> st;//棧保存計算結果int i = 0;//記錄下標while (i < n){//如果是空格，直接跳過！if (s[i] == ' ')i++;//如果是數字else if (s[i] >= '0' && s[i] <= '9'){//提取數字int val = 0;//保存數據while (s[i] >= '0' && s[i] <= '9'){val = val * 10 + (s[i] - '0');i++;}//判斷數字前面的運算符if (c == '+'){st.push(val);}else if (c == '-'){st.push(-val);}else if (c == '*'){st.top() *= val;}else if (c == '/'){st.top() /= val;}}//如果是其他，也就是運算符，更新符號else{c = s[i++];}}//取棧中元素相加，得到運算結果int ret = 0;while (!st.empty()){ret += st.top();st.pop();}//返回結果return ret;}
};

順利通過~這個題目也可以使用數組模擬棧實現功能，大家感興趣可以自己試一試~

字符串解碼😍

字符串解碼

? ? ? ? 我們需要根據要求進行字符串解碼，好在給出的字符串是沒有空格的，并且[ ]也是正確匹配的，我們可以進行分情況討論處理。

算法思路：分情況討論

①雙棧結構：使用兩個獨立棧協同工作

st_int：存儲數字（重復次數）

st_str：存儲字符串片段，初始化時st_str壓入空字符串""作為結果容器

②四類字符處理邏輯

數字（0-9）：
連續解析完整數字（如"12"→12），壓入st_int

左括號（[）：
提取后續連續小寫字母（如"[abc"→"abc"），作為新片段壓入st_str

小寫字母（a-z）：
直接拼接到st_str棧頂字符串末尾

右括號（]）：
彈出st_int棧頂數字n和st_str棧頂字符串s，將s重復n次后拼接到新棧頂

③嵌套解碼機制

遇到[時壓入新層級，遇到]時完成當前層級解碼：

內層字符串先解碼（如3[c]→"ccc"）

結果拼接到外層字符串（如"ab"+"ccc"→"abccc"）

支持任意深度嵌套（如3[a2[c]]→"accaccacc"）

④結果生成

最終返回st_str棧頂字符串：

初始空字符串作為基礎容器

所有層級解碼完成后棧頂即完整結果

時間復雜度O(n)，空間復雜度O(解碼字符串長度)

代碼實現：

//字符串解碼
class Solution
{
public:string decodeString(string s){stack<int> st_int;//保存數字stack<string> st_str;//保存字符串st_str.push("");//插入空字符串，分別后續變形int i = 0;while (i < s.size()){//分情況討論//如果是數字，提取數字入數字棧if (s[i] >= '0' && s[i] <= '9'){int tmp = 0;while (s[i] >= '0' && s[i] <= '9'){tmp = 10 * tmp + (s[i] - '0');i++;}st_int.push(tmp);}//如果是[,提取后續字符保存到字符棧else if (s[i] == '['){i++;string tmp;while (s[i] >= 'a' && s[i] <= 'z'){tmp += s[i];i++;}st_str.push(tmp);}//如果是字符，那么加到字符棧棧頂字符串末尾else if (s[i] >= 'a' && s[i] <= 'z'){st_str.top() += s[i];i++;}//如果是],就取數字棧和字符棧棧頂，進行拼接else if (s[i] == ']'){string s = st_str.top();int n = st_int.top();st_int.pop();st_str.pop();for (int j = 0; j < n; j++){st_str.top() += s;//新字符棧拼接重復的字符}i++;}}return st_str.top();//字符棧頂就是需要的結果}
};

順利通過~

驗證棧序列😝

驗證棧序列

? ? ? 我們以前都做過類似的文字題，那么使用代碼怎么解決呢？答案是進行模擬就可以了~

算法思路：使用棧模擬

①模擬核心邏輯：使用棧 st 實時模擬入棧/出棧操作，指針 i 跟蹤 popped 序列當前位置，驗證其合法性

②入棧與即時匹配：遍歷 pushed 序列：每個元素立即入棧，入棧后循環檢查：當棧非空且棧頂元素等于 popped[i] 時→ 彈出棧頂元素→ i 指針后移（匹配成功）

代碼實現：

//驗證棧序列
class Solution
{
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped){stack<int> st;int i = 0;//用于遍歷出棧序列for (auto& e : pushed)//遍歷進棧序列{st.push(e);while (st.size() && st.top() == popped[i]){st.pop();i++;}}//通過判斷棧是否為空或者i是否走到末尾判斷是否為合法出棧序列return st.empty();//return i==popped.size();}
};