2.1 什么是棧????????

????????有一種藝術(shù)叫做沙畫。把沙子一層一層的疊在一起，從而形成美麗的圖案。從圖中可以看到，最底層的深藍色沙子是最先放進去的。

?????????繼續(xù)放沙子，我們可以看到，最先放入的藍色沙子在底部，而最后放入的紫色沙子在頂部。

? ? ? ? 如果把頂部的沙子取出，又是怎樣的效果呢？

? ? ? ? 在此過程中，紫色沙子是最后放入的，卻是最先取出的，繼續(xù)取沙子，會觀察到下面的情況：

????????藍色沙子是最后取出的。只有一個出口，最先放入的元素（藍色沙子）最后取出(FIRST IN LAST OUT 先進后出)，最后放入的元素（紫色沙子）最先取出(LAST IN FIRST OUT 后進先出)的方式，這就是本章要講的棧。

? ? ? ? 把沙子放入桶的過程，叫做入棧，把沙子從桶中取出的過程，叫做出棧。

2.2 棧有什么用

2.2.1 歷史記錄（步驟回退）

? ? ? ? CTRL+Z是最常見的文本處理命令之一。甚至不止出現(xiàn)在文本軟件上，有編輯作用的軟件，例如圖片處理（PS），視頻剪輯（會聲會影,PE）軟件，通常也會有這個命令。簡單格式的軟件通常只支持一步回退動作，例如windows自帶的txt文本文件notepad.exe。

????????在益智小游戲，比如推箱子，五子棋，圍棋，井字棋中，往往會有個撤銷按鈕，這種時候，棧就可以派上用場了。下圖是井字棋下棋，以及棧操作撤銷的步驟：

?????????從圖中可以看到，撤銷的過程和下棋的過程恰好是相反的，符合棧中“先入后出”的規(guī)律。

? ? ? ? 附代碼：

public class Main {public static void main(String[] args){Main solution = new Main();System.out.println("開始井字棋游戲！");char[][] cs= new char[3][3];for(int i = 0; i < 3; i++){Arrays.fill(cs[i],'_');}solution.print(cs);Stack<char[][]> stack = new Stack<>();int type = 1;Scanner scanner = new Scanner(System.in);while(!solution.winOrLose(cs)){if(type==1){System.out.println("您現(xiàn)在是 X 棋");}else{System.out.println("您現(xiàn)在是 O 棋");}String s;if(!stack.isEmpty()){System.out.println("您需要進行什么操作？1 下棋 其他按鍵 撤銷");s = scanner.nextLine();}else{System.out.println();s = "1";}if("1".equals(s)){System.out.println("請輸入下棋位置，用逗號分隔：");int[] pos = new int[0];String line = scanner.nextLine();pos = solution.getPos(line);while (pos.length==0){System.out.println("您下棋的位置無效！請輸入下棋位置，用逗號分隔：");line = scanner.nextLine();pos = solution.getPos(line);}//壓棧stack.push(solution.copy(cs));cs[pos[0]][pos[1]] = type==1?'X':'O';type = -type;}else {//彈出cs = stack.pop();type = -type;}solution.print(cs);}System.out.println("贏家是"+ solution.winner+"的下棋者");}private char[][] copy(char[][] origin){char[][] copy = new char[3][3];for(int i = 0; i < 3;i++){for(int j = 0; j < 3; j++){copy[i][j] = origin[i][j];}}return copy;}char winner = ' ';private boolean winOrLose(char[][] cs){for(int i = 0; i < 3; i++){if(cs[i][0]!='_'&&cs[i][0]==cs[i][1]&&cs[i][1]==cs[i][2]){winner = cs[i][0];return true;}}for(int i = 0; i < 3; i++){if(cs[0][i]!='_'&&cs[0][i]==cs[1][i]&&cs[1][i]==cs[2][i]){winner = cs[0][i];return true;}}if(cs[0][0]!='_'&&cs[0][0]==cs[1][1] &&cs[1][1]==cs[2][2]){winner = cs[0][0];return true;}if(cs[0][2]!='_'&&cs[0][2]==cs[1][1] &&cs[1][1]==cs[2][0]){winner = cs[0][2];return true;}return false;}private int[] getPos(String str){if(!str.contains(","))return new int[0];String[] strs = str.split(",");if(isDigit(strs[0]) && isDigit(strs[1])){int a = Integer.parseInt(strs[0]);int b = Integer.parseInt(strs[1]);if(a>=0&&a<3&&b>=0&&b<3)return new int[]{a,b};}return new int[0];}private boolean isDigit(String s){try{int t = Integer.parseInt(s);}catch (Exception e){return false;}return true;}private void print(char[][] cs){for(int i = 0; i < 3; i++){for(int j = 0; j < 3;j++){System.out.print(cs[i][j]+" ");}System.out.println();}} }

2.2.2 配對

? ? ? ? 在使用計算器，文本，輸入代碼過程中，如果括號不匹配，會立刻給出提示。例如：

????????我們忽略文本中的字母部分，僅保留括號，可得到內(nèi)容: {{([]){(){}}????????

? ? ? ? 已知 ’{‘ 和 ’}‘ 是匹配的， ’[‘ 和 ’]‘ 是匹配的， '(' 和 ’)‘ 是匹配的。

????????在遇到右側(cè)括號時，如果沒有足夠的左側(cè)括號與其進行抵消，那說明是非法的；在遍歷完所有的括號之后，如果左側(cè)括號依然無法找到與之匹配的右側(cè)括號，那么說明左側(cè)括號是非法的。代碼如下，此處暫不深究，后續(xù)將做進一步說明：

public class Main {public static void main(String[] args) {Main main = new Main();System.out.println( main.checkCmp("public class Main{\n" +"\tpublic static void main(String[] args){\n" +"\t\tMain solution = new Main();{\n" +"\t}\n" +"}"));//多了一個左括號System.out.println( main.checkCmp("public class Main{\n" +"\tpublic static void main(String[] args){\n" +"\t\tMain solution = new Main();\n" +"\t}\n" +"}"));//正確的System.out.println( main.checkCmp("public class Main{\n" +"\tpublic static void main(String[] args){\n" +"\t\tMain solution = new Main();\n" +"\t}\n" +"}}"));//多了一個右括號}public boolean checkCmp(String str){if(str == null || str.isEmpty())return true;int n = str.length();Stack<Character> stack = new Stack<>();for(int i = 0; i < n; i++){char c = str.charAt(i);//左括號入棧if(c == '{' || c == '[' || c == '('){stack.push(c);//右括號出棧}else if(c == '}' || c == ']' || c ==')'){if(stack.isEmpty())return false;char p = stack.pop();if(c=='}' && p !='{')return false;if(c == ']' && p != '[')return false;if(c == ')' && p != '(')return false;}}return stack.isEmpty();}}

2.2.3 計算器

? ? ? ? 計算機最早的用途就是用于計算數(shù)值的。以一段簡單的 為例。當(dāng)遇到左括號的時候，把前面的累計結(jié)果對數(shù)字棧進行入棧 [2] ,符號棧也進行入棧 [x] ,算完括號的 ?的結(jié)果后，把兩個棧的結(jié)果彈出拿到 2 和符號 x?,然后用拿到的數(shù)字和符合，和后面計算過的數(shù)字進行運算，得到?。

2.2.4 遞歸????????

????????比如下面這段程序，是一段遞歸。完成了從 start 到 end 的累加過程。

public class Main {public static void main(String[] args){Main solution = new Main();System.out.println(solution.getSum(1,3));}private int getSum(int start, int end){if(start>end)return dfs(end,start);return dfs(start,end);}private int dfs(int start, int end){if(start == end)return start;return start+dfs(start+1,end);} }

????????下圖，是計算機實際的執(zhí)行過程：

?2.3?棧的操作

棧頂：棧最頂部的元素叫做 棧頂，指向棧頂元素的指針，叫做 棧頂指針。

出棧：把棧頂指針的元素取出的過程，把棧頂指針向下移動的過程，叫做?出棧。

入棧：把元素放入棧頂，并將棧頂指針向下移動的過程，叫做?入棧。

查看棧頂元素：查看棧頂指針對應(yīng)的元素內(nèi)容，這一過程只查看不進行出棧入棧操作。

棧空：棧中沒有元素，棧頂指針指向 NULL，無法進行出棧操作

棧滿：棧中數(shù)據(jù)已滿，無法再容納新的元素，無法進行入棧操作

這樣描述呢比較抽象，下面用比較形象的方式再進行一次敘述。

2.3.1 概念解讀

? ? ? ? 一串糖葫蘆最上面的那顆，我們下一顆可以吃掉的糖葫蘆，就是棧頂。它的特點是在頂部，是下一顆準備吃掉的目標。

? ? ? ? 最后一顆能吃掉的糖葫蘆就是?棧底。

? ? ? ? 吃掉糖葫蘆之前需要用自己銅鈴般水汪汪的大眼睛盯著，防止把糖葫蘆吃到鼻子里。這個“盯”，就是?棧頂指針?啦！

? ? ? ? 入棧 和 出棧 在本章開頭已經(jīng)有了較為詳盡的解釋，此處不再贅述。

? ? ? ? 棧滿 呢，就是剛拿到這串糖葫蘆的時候，它上面的尖頭已經(jīng)不足以再串一個新的糖葫蘆了，換句話說，就是串糖葫蘆的竹簽不夠長度再串一顆新的糖葫蘆了。

? ? ? ? 棧空，就是把這串糖葫蘆吃完了，沒有新的糖葫蘆可以吃，也沒有任何一顆糖葫蘆需要你繼續(xù)盯著。

2.3.2 棧的缺點

• 操作受限

? ? ? ? 棧只能做出查看 棧頂、入棧、出棧 三種操作，而且僅能對棧頂元素進行操作，實際能做的非常有限，需要一些特定場景才能起到作用。

• ?遞歸層次有限????????

????????如圖所示，遞歸調(diào)用不到10000層就發(fā)生了內(nèi)存溢出。

2.4 單調(diào)棧

????????棧內(nèi)的元素按照從棧底到棧頂?shù)捻樞?#xff0c;所有元素滿足單調(diào)遞增或者單調(diào)遞減或單調(diào)非遞增，單調(diào)非遞減時，可以稱之為單調(diào)棧。

2.4.1 什么時候可以用單調(diào)棧

? ? ? ? 事實上，在寫這篇文章之前，我也不知道什么是單調(diào)棧。但是既然決定了把單調(diào)棧作為書寫內(nèi)容之一，就有責(zé)任有義務(wù)把這個東西它什么時候能用具體的進行描述。只有這樣，單調(diào)棧這樣的神級工具，才能在合適的位置發(fā)揮最大作用。

????????如果一個問題可以轉(zhuǎn)化為，找到（上一個/下一個）（大于/小于）【等于】當(dāng)前值或者對應(yīng)的索引，就可以求出答案，那么單調(diào)棧就是你的最佳幫手。

? ? ? ? 如果是上一個，則從前往后遍歷。

? ? ? ? 如果是下一個，則從后往前遍歷。

? ? ? ? 其中等于這個條件可要可不要。

2.4.2 單調(diào)棧實踐

1475. 商品折扣后的最終價格https://leetcode-cn.com/problems/final-prices-with-a-special-discount-in-a-shop/

????????瀏覽了眾多有關(guān)單調(diào)棧的題目，力扣的這一題，感覺特別合適作為單調(diào)棧的講解題目。

????????為了方便讀者閱讀，本篇文章內(nèi)也引用一下題目內(nèi)容：

給你一個數(shù)組?prices?，其中?prices[i]?是商店里第?i?件商品的價格。

商店里正在進行促銷活動，如果你要買第?i?件商品，那么你可以得到與 prices[j] 相等的折扣，其中?j?是滿足?j > i?且?prices[j] <= prices[i]?的?最小下標?，如果沒有滿足條件的?j?，你將沒有任何折扣。

請你返回一個數(shù)組，數(shù)組中第?i?個元素是折扣后你購買商品 i?最終需要支付的價格。

? ? ? ? 首先進行一波題目解析：

? ? ? ? 輸入：數(shù)組 prices，每個元素代表價格

? ? ? ? 輸出：數(shù)組 ans，每個元素代表折扣后你購買商品 i?最終需要支付的價格

? ? ? ? 條件：

? ? ? ? 1. 商品可以得到折扣

? ? ? ? 2. 優(yōu)惠價格是在當(dāng)前索引后面的位置查找到第一個小于等于它的價格作為折扣

? ? ? ? 3. 沒有折扣的情況，折扣為0

? ? ? ? 4. 實際支付金額=原價-折扣

? ? ? ? 這題可以轉(zhuǎn)化為：找到下一個小于等于當(dāng)前價格的值，用當(dāng)前的價格找到下一個比它大的價格即為答案。

? ? ? ? 思路：

????????1.? 根據(jù)前面給的解題方式，描述時使用了 下一個，因此從后往前遍歷

? ? ? ? 2.? 應(yīng)為非遞增棧，從后往前遍歷，假設(shè) j1<=j2,且?prices[j1]?的值更小，那么對于任意一個比 j1?的索引更前的索引i，必然選擇 j1 的值,那么棧中所有比它大的元素都應(yīng)出棧

喜歡的話，點個贊吧~！平時做題，以及筆記內(nèi)容將更新到公眾號。

關(guān)注公眾號，互相學(xué)習(xí)：鈺娘娘知識匯總

總結(jié)

以上是生活随笔為你收集整理的【简约而不简单：神级代码的小秘密】| 第二章 栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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