一、 堆疊(Stack)

1、概念

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊
頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，

壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，

出堆疊：堆疊的洗掉操作叫做出堆疊，出資料在堆疊頂，

堆疊的特點是 先進后出

Java虛擬機堆疊：JVM stack 是JVM中的一塊記憶體，呼叫函式的時候，在JVM stack 開辟一塊記憶體，叫做堆疊幀

2、入堆疊和出堆疊的順序

一個堆疊的入堆疊序列是a b c d，堆疊不可能出堆疊序列為（）：
A. edcba
B.decba
C.dceab
D.abcde

一個堆疊的入堆疊序列是m n x y z，堆疊不可能出堆疊序列為（）：
A. mnxyz
B. xnyzm
C. nymxz
D. nmyzx

了解了堆疊的概念，解決以上問題

解釋：1. 入堆疊a b c d 此時d c出堆疊，e沒有，入堆疊再出堆疊，下一個a要出堆疊，先要出b，順序應該是ba，所以答案C錯誤
2. 同樣，答案C中，第一個出n，所以m壓堆疊，n壓堆疊再出堆疊，接著x壓堆疊，y壓堆疊再出堆疊，下一個要出m先得出x

3、中綴運算式轉后綴運算式

例如：求 (5 + 4) * 3 - 2的后綴運算式
做法：先按照運算順序加括號，再將所有運算子放到括號后，最后去除我們加上的括號
(((5 + 4) * 3) - 2)
(((5 4)+ 3)* 2)-
5 4+ 3 * 2 -

如果通過這個后綴運算式求值？
用 i 遍歷這個運算式，數字壓堆疊，遇到運算子，彈出堆疊頂的兩個元素，第一個放在運算子右邊，否則減法就會錯順序

4、堆疊的方法

public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        // 壓堆疊
        stack.push(11);
        stack.push(22);
        stack.push(33);
        // 彈出堆疊頂元素，并洗掉
        System.out.println(stack.pop()); // 33
        // 獲取堆疊頂元素，但不洗掉
        System.out.println(stack.peek()); // 22
        // 是否為空
        System.out.println(stack.empty()); // false
        // 查找
        System.out.println(stack.search(22)); // 1
    }

繼承的方法等：

LeetCode 150. 逆波蘭運算式求值

150. 逆波蘭運算式求值

根據 逆波蘭表示法，求運算式的值，
有效的算符包括 +、-、*、/ ，每個運算物件可以是整數，也可以是另一個逆波蘭運算式，

說明：
整數除法只保留整數部分，
給定逆波蘭運算式總是有效的，換句話說，運算式總會得出有效數值且不存在除數為 0 的情況，

示例 1：
輸入：tokens = [“2”,“1”,"+",“3”,"*"]
輸出：9
解釋：該算式轉化為常見的中綴算術運算式為：((2 + 1) * 3) = 9

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++) {
            String val = tokens[i];
            if(!isOperation(val)) {
                // 不是運算子
                stack.push(Integer.parseInt(val)); // 轉為數字
            } else {
                // 是運算子 計算
                int num1 = stack.pop();
                int num2 = stack.pop();
                switch(val) {
                    case "+":
                      stack.push(num2 + num1);
                      break;
                    case "-":
                        stack.push(num2 - num1);
                        break;
                    case "*":
                        stack.push(num2 * num1);
                        break;
                    case "/":
                        stack.push(num2 / num1);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperation(String x) {
        if(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
            return true;
        }
        return false;
    }
}

劍指 Offer 31. 堆疊的壓入、彈出序列

劍指 Offer 31. 堆疊的壓入、彈出序列

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

示例 1：
輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
輸出：true
解釋：我們可以按以下順序執行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]); // 遍歷pushA陣列 放入堆疊中
            // 回圈判斷 堆疊頂元素和當前 j 下標是否一樣 一樣就彈出
            while(!stack.empty() && j < popped.length && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

5、堆疊的實作

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[5];
    }

    public void push(int val) {
        if(isFull()) { // 2被擴容
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
    }

    // 判斷陣列滿
    public boolean isFull() {
        return this.usedSize == this.elem.length;
    }

    public int pop() {
        if(isEmpty()) {
            throw new RuntimeException("堆疊為空");
        }
        int oldVal = this.elem[usedSize - 1];
        this.usedSize--;
        return oldVal;
    }

    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("堆疊為空");
        }
        return this.elem[usedSize - 1];
    }

    // 判斷空
    public boolean isEmpty() {
        return this.usedSize == 0;
    }
}

LeetCode 20. 有效的括號

20. 有效的括號

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

有效字串需滿足：
左括號必須用相同型別的右括號閉合，
左括號必須以正確的順序閉合，

示例 1：
輸入：s = “()”
輸出：true

class Solution {
    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; // 右括號多
                }
                char top = stack.peek(); // 堆疊頂元素
                if(top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}') {
                    stack.pop();
                } else {
                    return false; // 左右括號不匹配
                }
            }
        }
        return stack.empty(); // 不為空 左括號多
    }
}

LeetCode 155. 最小堆疊

155. 最小堆疊

設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的堆疊，

push(x) —— 將元素 x 推入堆疊中，
pop() —— 洗掉堆疊頂的元素，
top() —— 獲取堆疊頂元素，
getMin() —— 檢索堆疊中的最小元素，

示例:
輸入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

輸出：
[null,null,null,null,-3,null,0,-2]

class MinStack {

    // private Stack<Integer> stack = new Stack<>();
    // private Stack<Integer> minStack = new Stack<>();
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(!minStack.empty()) { // 不為空
            int top = minStack.peek();
            if(val <= top) { // 小于等于 也要放進去
                minStack.push(val);
            }
        } else {
            minStack.push(val);
        }
    }
    
    public void pop() {
        int popVal = stack.pop();
        if(!minStack.empty()) {
            int top = minStack.peek();
            if(top == popVal) {
                minStack.pop();
            }
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

二、佇列

1、普通佇列 與 雙端佇列

佇列：（queue）只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(First
In First Out) 入佇列：進行插入操作的一端稱為隊尾（Tail/Rear） 出佇列：進行洗掉操作的一端稱為隊頭
（Head/Front）

雙端佇列：（deque）是指允許兩端都可以進行入隊和出隊操作的佇列，deque 是 “double ended queue” 的簡稱，
那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊，

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class TestDemo {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        // 入佇列
        queue.add(1); // 容量限制 -> 可能對拋例外
        queue.offer(2);
        // 獲取隊首元素
        System.out.println(queue.peek()); // 1
        System.out.println(queue.element()); // 1
        // 出佇列
        System.out.println(queue.poll()); // 1
        System.out.println(queue.remove()); // 2

        System.out.println("================");

        Deque<Integer> queue2 = new LinkedList<>();
        queue2.offerFirst(1);
        queue2.offerFirst(2);
        queue2.offer(3); // 默認隊尾入隊
        // 2 1 3
        System.out.println(queue2.peek()); // 2 默認獲取隊首元素
        System.out.println(queue2.peekFirst()); // 2
        System.out.println(queue2.peekLast()); // 3
    }
}

2、單鏈表實作佇列

對LinkedList來說，不僅可以當做普通的佇列，也可以當做雙端佇列，也可以當做雙向鏈表，也可以當做堆疊，

用單鏈表來實作佇列，用一個last 指標實作時間復雜度O(1)

class Node {
    public int val;
    public Node next;
    public Node(int val) {
        this.val = val;
    }
}

public class MyQueue {
    public Node head;
    public Node last;

    /**
     * 尾插
     * @param val
     */
    public void offer(int val) {
        Node node = new Node(val);
        if(this.head == null) {
            this.head = node;
            last = node;
        } else {
            last.next = node;
            last = last.next;
        }
    }

    /**
     * 出佇列
     * @return
     */
    public int poll() {
        if(isEmpty()) {
            throw new RuntimeException("佇列為空");
        }
        int oldVal = head.val;
        this.head = head.next;
        return oldVal;
    }

    public boolean isEmpty() {
        return this.head == null;
    }

    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("佇列為空");
        }
        return head.val;
    }
}

// 測驗：
public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue.poll()); // 1
        System.out.println(queue.poll()); // 2
        System.out.println(queue.poll()); // 3
}

3、 回圈佇列

如何區分空與滿：

• 第一種解決方式：使用usedSize.使用usedSize和陣列長度比較，確定滿或者空，

• 第二種解決方式：使用標志位

• 第三種解決方式：保留一個位置 front == rear
  每次存放元素之前，都先檢查一下rear的下一個是不是front，如果是那么就是滿的，

LeetCode 622. 設計回圈佇列

622. 設計回圈佇列

你的實作應該支持如下操作：

MyCircularQueue(k): 構造器，設定佇列長度為 k ，
Front: 從隊首獲取元素，如果佇列為空，回傳 -1 ，
Rear: 獲取隊尾元素，如果佇列為空，回傳 -1 ，
enQueue(value): 向回圈佇列插入一個元素，如果成功插入則回傳真，
deQueue(): 從回圈佇列中洗掉一個元素，如果成功洗掉則回傳真，
isEmpty(): 檢查回圈佇列是否為空，
isFull(): 檢查回圈佇列是否已滿，

class MyCircularQueue {

    public int[] elem;
    public int front; // 對頭下標
    public int rear; // 隊尾下標

    public MyCircularQueue(int k) {
        this.elem = new int[k + 1]; // k + 1
    }

    // 入佇列
    public boolean enQueue(int value) {
        if(isFull()) return false;
        this.elem[rear] = value;
        rear = (rear + 1) % elem.length;
        return true;
    }

    // 出佇列
    public boolean deQueue() {
        if(isEmpty()) return false;
        front = (front +  1) % elem.length;
        return true;
    }

    // 得到隊頭元素
    public int Front() {
        if(isEmpty()) return -1;
        return elem[front];
    }

    // 得到隊尾元素
    public int Rear() {
        if(isEmpty()) return -1;
        int index = -1;
        if(rear == 0) {
            index = elem.length - 1;
        } else {
            index = rear - 1;
        }
        return elem[index];
    }

    public boolean isEmpty() {
        return front == rear; // 相遇
    }

    public boolean isFull() {
        // rear 的下一個是 front
        if((this.rear + 1) % elem.length == front) {
            return true;
        }
        return false;
    }
}

LeetCode 225. 用佇列實作堆疊

225. 用佇列實作堆疊

// 入堆疊時，入到不為空的佇列，都為空就指定一個
// 出堆疊時，在不為空的佇列，出 size - 1 個元素，剩下的一個就是要出堆疊的元素
public class MyStack {

    public Queue<Integer> qu1;
    public Queue<Integer> qu2;

    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    public void push(int x) {
        if(!qu1.isEmpty()) {
            qu1.offer(x);
        } else if (!qu2.isEmpty()) {
            qu2.offer(x);
        } else {
            qu1.offer(x); // 都為空 指定一個
        }
    }

    public int pop() {
        if(empty()) return -1;

        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for (int i = 0; i < size - 1; i++) {
                int val = qu1.poll();
                qu2.offer(val);
            }
            return qu1.poll();
        }
        if(!qu2.isEmpty()) {
            int size = qu2.size();
            for (int i = 0; i < size - 1; i++) {
                int val = qu2.poll();
                qu1.offer(val);
            }
            return qu2.poll();
        }

        return -1;
    }

    public int top() {
        if(empty()) return -1;

        if(!qu1.isEmpty()) {
            int val = -1;
            int size = qu1.size();
            for (int i = 0; i < size; i++) {
                val = qu1.poll();
                qu1.offer(val);
            }
            return val;
        }
        if(!qu2.isEmpty()) {
            int val = -1;
            int size = qu2.size();
            for (int i = 0; i < size; i++) {
                val = qu2.poll();
                qu1.offer(val);
            }
            return val;
        }

        return -1;
    }

    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

LeetCode 232. 用堆疊實作佇列

添加鏈接描述

class MyQueue {
    // 入隊的時候，統一入到第1 個堆疊
    // 出隊的時候，統一出第2 個堆疊的元素，如果第二個堆疊為空，將第1 個堆疊的所有元素匯入，再出堆疊頂元素，相當于倒了個順序
    public Stack<Integer> stack1;
    public Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if(empty()) return -1;

        if(stack2.empty()) {
            while(!stack1.empty()) {
                // int val = stack1.pop();
                // stack2.push(val);
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if(empty()) return -1;
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.empty() && stack2.empty();
    }
}