概念

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧
頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據在棧頂。

類似于子彈裝在彈夾里，先壓進去的，總是最后出來，棧也是這樣，遵從先進后出的原則。

目錄

概念

1.改變元素的序列

2. 將遞歸轉化為循環

3. 括號匹配?

4. 逆波蘭表達式求值

題目描述

5. 出棧入棧次序匹配

題目描述

---

?

1.改變元素的序列

這是一道選擇題，需要注意的是題目為進棧的過程可以出棧。

A選項為1,4,3,2，第一個出的為1，我們要把1先入棧然后在出棧，第二個為4，我們要把2,3,4依次入棧，然后依次出棧，從頂部出，正好為4,3,2,。因此A滿足。

B選項為2,3,4,1，第一個出的為2，我們要把1,2依次入棧，然后才能出一個2，此時棧內還有一個1，第二個出的為3，我們要把3入棧再出棧，第三個為4，把4入棧再出棧1最后把1出棧。因此B滿足。

C選項為3,1,4,2，第一個出的為3，我們就要把1,2,3，依次入棧，然后出一個3，第二個出的為1，但此時在棧頂的為2，且1比2先入棧，所以1不能先出棧。因此C不滿足，此題選C。

D選項為3,4,2,1，第一個出的為3，我們把1,2,3依次入棧，然后出一個3，此時1,2還在棧中，第二個出的為4，我們把4入棧在出棧，接著為2,1我們把棧內的1,2從棧頂出棧就能得到。因此D滿足。

---

?這道題需要注意的是，他是依次入棧，再依次出棧。

依次入棧，再從棧頂依次出棧，順序則為EDCBA54321，此題選B。

---

2. 將遞歸轉化為循環

比如：逆序打印鏈表

//遞歸方式public void printList(ListNode head){if(head.next!=null){printList(head.next);}System.out.print(head.val+" ");}

遞歸方式很簡單，條件為head.next不為空，就遞歸到head.next，直到走到最后一個開始打印，然后往回打印。

public void pintList(ListNode head){ListNode cur=head;Stack<ListNode> stack=new Stack<>();//依次入棧while(cur!=null){stack.push(cur);cur=cur.next;}//出棧且打印while (!stack.empty()){System.out.print(stack.pop().val+" ");}}

如果用棧來解決，首先將鏈表都遍歷一遍，全部依次入棧，最后一個元素正好在棧頂，然后在依次出棧并打印即可，這樣就將遞歸改做了循環，用棧來實現。

運行結果

---

3. 括號匹配
?

給定一個只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。

左括號必須以正確的順序閉合。

public boolean isValid(String s) {Stack<Character> stack=new Stack<>();for(int i=0;i < s.length();i++){char ch=s.charAt(i);if(ch=='('||ch=='['||ch=='{'){stack.push(ch);}else{if(stack.empty()){return false;}if(ch==')'&&stack.peek()=='('||ch==']'&&stack.peek()=='['||ch=='}'&&stack.peek()=='{'){stack.pop();}else{return false;}}}if(stack.empty()){return true;}return false;}

??

有了以上的分析結果，我們首先定義棧，遍歷字符串拿到的是字符，所以類型應該定義為Character。接著我們便利字符串，進入循環，我們定義ch用來接收取到的字符，用charAt（）轉換為字符，接著判斷是否為左括號（‘（’ ‘[’ '{'）,如果是，直接入棧，不是我們再進行那四種結果的判斷，如果此時棧空了，則說明右括號多了，如果此時左右括號匹配我們就出棧，如果不匹配，棧也沒空就說明左右括號不匹配。走完循環說明字符串已經便利完成，且之前的都匹配成功，我們在判斷棧是否為空，如果為空，說明此時正好都匹配成功，如果不為空就說明左括號多了。

---

4. 逆波蘭表達式求值

逆波蘭表達式又叫做后綴表達式。逆波蘭表示法是波蘭邏輯學家J?盧卡西維茲(J? Lukasiewicz)于1929年首先提出的一種表達式的表示方法?。后來,人們就把用這種表示法寫出的表達式稱作“逆波蘭表達式”。逆波蘭表達式把運算量寫在前面,把算符寫在后面。

題目描述

根據 逆波蘭表示法，求表達式的值。

有效的算符包括?+、-、*、/?。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。

注意?兩個整數之間的除法只保留整數部分。

可以保證給定的逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數值且不存在除數為 0 的情況。

public int evalRPN(String[] tokens) {Stack <Integer>stack=new Stack<>();for (String x:tokens){if(!isSymbol(x)){stack.push(Integer.parseInt(x));}else{//為+-*/int num2=stack.pop();int num1=stack.pop();switch(x){case "+":stack.push(num1+num2);break;case "-":stack.push(num1-num2);break;case "*":stack.push(num1*num2);break;case "/":stack.push(num1/num2);break;}}}return stack.peek();}private boolean isSymbol(String x){if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){return true;}return false;}

根據分析結果 ，我們首先定義棧，由于是數字運算，只有數字入棧，我們將棧定義為Integer類型，接著我們用for each來遍歷字符串數組，進入循環，我們要判斷此時的x為數字還是運算符，這里我寫了一個private修飾的方法來判斷。判斷后，如果是數字我們就將它入棧，如果不是數字就是運算符，我們應該switch語句進行匹配，匹配到哪個運算符就執行哪個運算符的操作。將運算結果在入棧，循環走完，說明數組遍歷完成，最后棧中的數據就為最終中綴表達式的計算結果。

注意：

判斷是否為運算符時要用equals（）方法。

入棧時要用Integer.parseInt(x)將字符串轉為整形。

最終結果就為棧中最后的數據。

---

5. 出棧入棧次序匹配

題目描述

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。

1. 0<=pushV.length ==?popV.length <=1000

2. -1000<=pushV[i]<=1000

3.?pushV?的所有數字均不相同

public boolean IsPopOrder(int [] pushA,int [] popA) {Stack<Integer> stack=new Stack<>();int j=0;for(int i=0;i<pushA.length;i++){stack.push(pushA[i]);while(j<popA.length&&!stack.empty()&&stack.peek()==popA[j]){stack.pop();j++;}}if(stack.empty()){return true;}return false;}

?

思路，有了我們先遍歷pushA數組將其中數據依次入棧，入棧一個，進入循環，再對棧頂的值與popA[]中的元素比較，如果等于就出棧一個。j從0開始，由于可能會連續匹配到，連續出棧，所以得用循環，如果前一個匹配到了，才能對popA中下一個值進行匹配。因此循環條件應該為: ?
j<popA.length&&!stack.empty()&&stack.peek()==popA[j]

首先數組不能越界，還有棧中也不能為空，接著就要與棧頂值進行比較，匹配了出棧頂值，j++。
最后兩個循環走完看棧是否空，如果空，說明都匹配到了，如果不為空，說明還有未匹配到的說明次序不對。

?

?

總結

以上是生活随笔為你收集整理的栈的应用场景（高频面试题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。