一.棧 · stack
1.概念
棧 :
- 一種特殊的線性表 , 其只允許再固定的一段進行插入和刪除元素操作?
- 進行數據插入和刪除操作的一段稱為 棧頂? ; 另一端稱為棧底
- 棧中的數據元素遵循 先進后出 原則(LIFO)
- 壓棧 : 棧的插入操作叫做 進棧 或 壓棧 或 入棧 , 入數據在棧頂
- 出棧 : 棧的刪除操作叫做 出棧 , 出數據在棧頂
2.棧的主要方法
| 方法 | 功能 |
|---|---|
| Stack() | 構造一個空的棧 |
| E push(E e) | 將 e 入棧，并返回 e |
| E pop() | 將棧頂元素出棧并返回 |
| E peek() | 獲取棧頂元素 |
| int size() | 獲取棧中有效元素個數 |
| boolean empty() | 檢測棧是否為空 |
public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(11);stack.push(12);stack.push(13);stack.push(14);System.out.println(stack);System.out.println(stack.size());System.out.println(stack.peek());stack.pop();}3.棧的模擬實現
Stack 繼承了 Vector(動態順序表)
import java.util.Arrays;public class MyStack {public int[] elem;public int usedSize;public MyStack(){this.elem = new int[10];}public boolean isFull(){return this.elem.length == usedSize;}//將 元素 val 入棧 , 并返回public void push(int val){if(isFull()){//判滿this.elem = Arrays.copyOf(elem,elem.length*2);//滿了則擴大為原來的兩倍}this.elem[usedSize++] = val;//后置++ , 先使用usedSize , 再+1}public boolean empty(){return usedSize == 0;//判斷是否為空 , 空返回true , 非空返回false}public int pop(){//將棧頂元素取出 , 并返回if(empty()){throw new EmptyStackException();}else{int val = elem[usedSize-1];usedSize--;return val;}}public int peek(){//獲取棧頂元素if(empty()){throw new EmptyStackException();}else{return elem[usedSize];}}}
public class EmptyStackException extends RuntimeException{public EmptyStackException() {super();}public EmptyStackException(String message) {super(message);}
}- 測試:
public class Test {public static void main(String[] args) {MyStack myStack = new MyStack();myStack.push(11);myStack.push(12);myStack.push(13);myStack.push(14);System.out.println(myStack);//打印棧的元素System.out.println(myStack.pop());//打印棧頂的元素 , 并將棧頂元素取出System.out.println(myStack);System.out.println(myStack.peek());//打印棧頂的元素}
}4.棧的應用場景
①改變元素序列
②將遞歸化為循環
// 遞歸方式
void printList(Node head) {if (null != head) {printList(head.next);System.out.print(head.val + " ");}
}// 循環方式
void printList(Node head) {if (null == head) {return;}Stack<Node> s = new Stack<>();// 將鏈表中的結點保存在棧中Node cur = head;while (null != cur) {s.push(cur);cur = cur.next;}// 將棧中的元素出棧while (!s.empty()) {System.out.print(s.pop().val + " ");}
}③括號匹配問題
題目:
- 給定一個只包括?
'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。 - 有效字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
- 每個右括號都有一個對應的相同類型的左括號
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(stack.empty()){return false;}char c2 = stack.peek();if(c1 == ')' && c2 == '('|| c1 == '}' && c2 == '{'|| c1 == ']' && c2 == '['){stack.pop();}else {return false;}}}if(!stack.empty()){return false;}return true;}④棧的壓入、彈出序列
題目:
- 輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序
- 假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。
- 0<=pushV.length ==?popV.length <=1000
- ?-1000<=pushV[i]<=1000
- ?pushV?的所有數字均不相同
public boolean IsPopOrder (int[] pushV, int[] popV) {Stack <Integer> stack = new Stack<>();int j = 0;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(!stack.empty()&&j < popV.length&&stack.peek() == popV[j]){stack.pop();j++;}}return stack.empty() ;}⑤逆波蘭表達式求值
- 中綴表達式求值
逆波蘭表達式求值:
- 將這些字符從左到右依次放到棧中
- 其中數字放到棧中 , 遇到算數符號時 , 取出兩個棧頂的元素
- 其中最上方的元素作為運算符的左操作數,下一個元素作為右操作數 , 再把得到的結果放回棧中
- 繼續重復操作
題目:
給你一個字符串數組?tokens?，表示一個根據?逆波蘭表示法?表示的算術表達式。
請你計算該表達式。返回一個表示表達式值的整數。
注意：
- 有效的算符為?
'+'、'-'、'*'?和?'/'?。 - 每個操作數（運算對象）都可以是一個整數或者另一個表達式。
- 兩個整數之間的除法總是?向零截斷?。
- 表達式中不含除零運算。
- 輸入是一個根據逆波蘭表示法表示的算術表達式。
- 答案及所有中間計算結果可以用?32 位?整數表示。
public boolean isoperation(String s){if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){return true;}else {return false;}}public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>() ;for (String c:tokens) {if(!isoperation(c)){int x = Integer.parseInt(c);stack.push(x);}else {int val2 = stack.pop();int val1 = stack.pop();switch (c){case "+":stack.push(val1+val2);break;case "-":stack.push(val1-val2);break;case "*":stack.push(val1*val2);break;case "/":stack.push(val1/val2);break;}}}return stack.pop();}
)
)
