棧的底層原理
棧（Stack）是一種后進先出（LIFO）?的線性數據結構，所有操作（如插入、刪除）僅在棧頂進行。它的底層實現可以是數組或鏈表，具體取決于編程語言和應用場景。
1.基于數組實現：使用連續內存的數組存儲元素，通過一個指針（如?top）標記棧頂位置。
核心操作：入棧（Push）?：將元素放入?top?位置，top?指針后移。?
出棧（Pop）?：返回?top-1?位置的元素，top?指針前移。
2. 基于鏈表（鏈式存儲）:使用單向鏈表（頭插法）存儲元素，鏈表的頭節點作為棧頂。
入棧（Push）?：將新節點插入鏈表頭部。
?出棧（Pop）?：刪除鏈表頭節點并返回其值。
棧的應用場景
函數調用與遞歸：操作系統自動管理函數調用棧。
?括號匹配：檢查表達式中的括號是否成對。
?表達式求值：中綴表達式轉后綴表達式（逆波蘭式）。
?撤銷操作（Undo）?：編輯器中的操作歷史棧。
?深度優先搜索（DFS）?：用棧保存遍歷路徑
對應題目?
用棧實現隊列用棧實現隊列用棧實現隊列
思想：用兩個棧來模擬隊列，由于隊列是先進先出，所以設置兩個棧，一個入隊棧，一個出隊棧
import java.util.Deque;
import java.util.ArrayDeque;class MyQueue {private Deque<Integer> inputStack;private Deque<Integer> outputStack;public MyQueue() {inputStack = new ArrayDeque<>();outputStack = new ArrayDeque<>();}// 入隊：直接壓入輸入棧public void push(int x) {inputStack.push(x);}// 出隊：若輸出棧為空，先轉移元素public int pop() {if (outputStack.isEmpty()) {transferInputToOutput();}return outputStack.pop();}// 查看隊首元素：類似出隊但不刪除public int peek() {if (outputStack.isEmpty()) {transferInputToOutput();}return outputStack.peek();}// 判斷隊列是否為空public boolean empty() {return inputStack.isEmpty() && outputStack.isEmpty();}// 將輸入棧元素轉移到輸出棧（反轉順序）private void transferInputToOutput() {while (!inputStack.isEmpty()) {outputStack.push(inputStack.pop());}}
}用隊列實現棧用隊列實現棧用隊列實現棧用隊列實現棧
思想：隊列模擬棧，使用兩個隊列來模擬，一個主隊列，一個副隊列
核心思想
- 維護兩個隊列：一個主隊列（
mainQueue）和一個輔助隊列（tempQueue）。 - ?入棧（Push）?：直接將元素加入主隊列。
- ?出棧（Pop）?：將主隊列中除最后一個元素外的所有元素轉移到輔助隊列，彈出最后一個元素，最后交換主隊列和輔助隊列的角色。
?操作步驟
- ?Push（入棧）?：
- 將新元素直接加入主隊列。
- ?Pop（出棧）?：
- 將主隊列中的前?
n-1?個元素依次出隊并加入輔助隊列。 - 彈出主隊列的最后一個元素（即棧頂元素）。
- 交換主隊列和輔助隊列的角色，以便下次操作。
-
import java.util.LinkedList; import java.util.Queue;class MyStack {private Queue<Integer> mainQueue;private Queue<Integer> tempQueue;public MyStack() {mainQueue = new LinkedList<>();tempQueue = new LinkedList<>();}// 入棧：直接加入主隊列public void push(int x) {mainQueue.offer(x);}// 出棧：轉移前n-1個元素后彈出最后一個元素public int pop() {while (mainQueue.size() > 1) {tempQueue.offer(mainQueue.poll());}int top = mainQueue.poll();// 交換主隊列和輔助隊列Queue<Integer> swap = mainQueue;mainQueue = tempQueue;tempQueue = swap;return top;}// 查看棧頂元素：邏輯同pop，但需將元素重新放回主隊列public int top() {while (mainQueue.size() > 1) {tempQueue.offer(mainQueue.poll());}int top = mainQueue.poll();tempQueue.offer(top); // 重新加入隊列// 交換隊列Queue<Integer> swap = mainQueue;mainQueue = tempQueue;tempQueue = swap;return top;}// 判空：主隊列是否為空public boolean empty() {return mainQueue.isEmpty();} }
- 將主隊列中的前?
有效的括號有效的括號
思想：括號匹配是使用棧解決的經典問題。遇見左括號就壓入棧中，遇見右括號，先判斷棧是否為空，在導出棧頂元素判斷，若最后棧為空則說明符號匹配成功，若左右括號不匹配也返回失敗。
class Solution {public boolean isValid(String s) {Stack<Character> stack =new Stack<>();for (int i=0;i<s.length();i++){char c1 = s.charAt(i);if(c1 =='{' ||c1 =='(' ||c1 =='['){stack.push(c1);}else if(c1 =='}' ||c1 ==')' ||c1 ==']'){if(stack.isEmpty()){return false;}else if (stack.peek() =='{' && c1 =='}'){stack.pop();}else if (stack.peek() =='(' && c1 ==')'){stack.pop();}else if (stack.peek() =='[' && c1 ==']'){stack.pop();}else{return false;}}}return stack.isEmpty();}
}刪除字符串中的所有相鄰重復項?
思想：比較簡單，需要注意一個點就是，棧無法直接轉化成數組，即stack.toString()是錯誤的
要創建數組，將棧中的元素都出棧即可
class Solution {public String removeDuplicates(String s) {Stack<Character> stack =new Stack<>();for(int i=0;i<s.length();i++){char c = s.charAt(i);if(stack.isEmpty() || c != stack.peek()){stack.push(c);}else {stack.pop();}}String str = "";//剩余的元素即為不重復的元素while (!stack.isEmpty()) {str = s.pop() + str;}return str;}
}逆波蘭表達式求值
要注意下述代碼中的幾個問題：
1.因為字符串表示的是整數的加減乘除運算，所以定義棧的時候要采取整型Stack<Integer> stack =new Stack<>();
2.定義兩個變量分別存儲前兩個操作數，但要注意操作數的順序，因為先進后出，所以第一個出來的是第二個操作數
3.巧用switch分支結構，先做判斷，在壓入棧
4.最后不是輸出整個棧的元素，方法要求的返回表達式值的整數，所以要做類型轉換Integer.valueOf(token)
5.由于leetcode 內置jdk的問題，不能使用==判斷字符串是否相等，只能用equals。并且字符相等用雙引號
class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack =new Stack<>();int a,b,c;for(String token :tokens){if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/") ){b = stack.pop();//第二個操作數a = stack.pop();//第一個操作數c = switch(token){case "+" -> a+b;case "-" -> a-b;case "*" -> a*b;case "/" -> a/b;default -> 0;};stack.push(c);}else {stack.push(Integer.valueOf(token));}}return stack.pop();}
}有效的括號用隊列實現棧用隊列實現棧用隊列實現棧
