棧

什么是棧

這里的棧與我們之前常說的棧是不同的。之前我們說的棧是內存棧，它是JVM內存的一部分，用于存儲局部變量、方法調用信息等。每個線程都有自己獨立的棧空間，當線程啟動時，棧就會被創建；線程結束，棧也會被銷毀。
而數據結構中的棧是一種抽象數據類型，描述的是一種存儲數據的一種方法，遵循“先進后出”的原則，是一種線性的數據結構。

像上圖所示就是一個棧，只能對于頂部完成操作，放元素放在最上面，當要拿棧中的元素也只能從最上面的元素開始獲取。

官方棧

Stack類中的方法

方法	功能
Stack()	構造方法
E push(E e)	將e入棧
E pop()	將棧頂元素出棧并返回
E peek()	獲取棧頂元素
int size	獲取棧中的有效元素個數
boolean empty()	棧中是否為空
int search(Object o)

代碼展示：

public static void test1() {Stack<Integer> stack = new Stack<>();stack.push(10);stack.push(20);stack.push(30);stack.push(40);stack.pop();System.out.println(stack);//[10, 20, 30]System.out.println(stack.size());//3System.out.println(stack.peek());//30System.out.println(stack.empty());//falseSystem.out.println(stack.search(10));//3
}

代碼解釋：

1、對于search方法的返回：如果對象存在于棧中，會返回該對象到棧頂的距離（棧頂元素的距離為 1）；若對象不在棧中，則返回 -1。
2、由于Stack繼承了Vector等其他類，也可以調用Vecto等其他類中的方法。

用數組自己實現一個棧

代碼展示：

import java.util.Arrays;
public class MyStack<E> {private Object[] elem;private int useSize;public static final int DEFAULT_CAPACITY = 10;public MyStack() {elem = new Object[DEFAULT_CAPACITY];}/*** 完成入棧操作*/public void push(E data) {if(isFull()) {elem = Arrays.copyOf(elem,elem.length*2);}elem[useSize] = data;useSize++;}/*** 完成出棧操作，將棧頂的元素出棧并返回*/public E pop() {if(isEmpty()) {return null;}E ret = (E)elem[useSize - 1];useSize--;return ret;}/*** 返回棧頂的元素*/public E peek() {if(elem == null) {return null;}return (E)elem[useSize - 1];}/*** 棧中的元素個數* @return*/public int size() {return useSize;}private boolean isFull() {return elem.length == useSize;}public boolean isEmpty() {return useSize == 0;}public void display() {for (int i = 0; i < useSize; i++) {System.out.print(elem[i] + " ");}System.out.println();}
}

代碼解釋：

1、定義的 MyStack 類屬于泛型類，也就是 MyStack<E>，E 代表元素的類型，不過在編譯時具體類型是未知的。Java 并不允許創建泛型數組，也就是不能直接寫 E[] elem = new E[DEFAULT_CAPACITY]; 。這是由于 Java 的泛型是通過類型擦除來實現的，在運行時泛型類型信息會被擦除，因此無法創建泛型數組。此時，借助 Object 數組，能夠存儲任意類型的對象。
2、Stack類底層使用數組實現的，當然我們也可以用鏈表實現Stack類。
3、 我們也可以使用鏈表的形式實現棧，在LinkedList類中也有push、pop、peek方法等方法。

棧的使用

1、用棧實現逆序打印鏈表

對于之前實現是通過遞歸的方法

public void printList(ListNode head) {ListNode cur = head;if(head != null) {printList(cur.next);System.out.print(cur.value + " ");}
}

通過遞歸回代的機制實現鏈表的逆序打印。
這也可以看成先進后出的。正序是從頭開始打印，先將元素放在棧中，在開始取出元素，取出的元素對于鏈表來說就是逆序輸出。

public void print(ListNode head) {ListNode cur = head;if(head == null) {return;}Stack<ListNode> stack = new Stack<>();//從頭節點開始依次存入棧中while (cur != null) {stack.push(cur);cur = cur.next;}//開始取出元素，此時取出的是鏈表中最后的節點，因為它是最后放入棧中的while (!stack.empty()) {System.out.print(stack.pop().value + " ");}System.out.println();
}

2、逆波蘭表達式

逆波蘭表達式也叫后綴表達式。我們平常算數用的是中綴表達式(例如：1 + 2 = 3)。關于后綴表達式怎么從中綴表達式得來的，可以自行百度。下面是豆包給出來的運算方法。

代碼展示：

public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(String string : tokens) {if(!isOperations(string)) {//是數字將其存入棧中stack.push(Integer.parseInt(string));}else {//是操作符，取出兩個數字進行計算，將運算的數字在存入棧中int right = stack.pop();int left = stack.pop();switch (string){case "+" :stack.push(left + right);break;case "-" :stack.push(left - right);break;case "*" :stack.push(left * right);break;case "/" :stack.push(left / right);break;}}}//返回棧中最后一個元素了return stack.pop();
}
private boolean isOperations(String string) {return string.equals("+") || string.equals("-") || string.equals("*") || string.equals("/");
}

3、棧的壓入與彈出序列

代碼展示：

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();
}

代碼解釋：

for循環是將pushV數組中的元素依次放在棧中。while循環是按照popV數組取出來的，當棧頂上的元素等于popV中的第一個元素，就從棧中取出，popV往后走。為什么判斷條件要有!stack.empty()？是因為防止stack.peek()為空指針異常。

4、最小棧

代碼展示：

class MinStack {Stack<Integer> stack;Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if(minStack.empty()) {minStack.push(val);}else {if(val <= minStack.peek()) {minStack.push(val);}}}public void pop() {int popVal = stack.pop();if(popVal == minStack.peek()) {minStack.pop();}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

代碼解釋：

1、在push()方法中將小的之push到minStack棧中。此時需要注意的是，當有兩個緊挨一樣的最小值，它們都需要push到minStack棧中，因為當stack棧中pop了這個值，但最小值還是它。
2、在pop方法中if語句的判斷條件需要注意。由于棧中存儲的是Integer類對象，比較時不能直接用等號（stack.pop() == minStack.peek()像這樣是錯的）。可以定義int類型的臨時變量，在比較的時候Integer類型的會自動拆箱。（在push方法中if語句比較也是一樣的）