1. 堆疊

1.1 概念

一種特殊的線性表，說明了具有前驅和后繼關系，只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉的一端稱為堆疊頂，另一端稱為堆疊底，
堆疊中的資料元素遵循后進先出 LIFO 原則【Last In First Out】
壓堆疊：堆疊的插入/進堆疊/壓堆疊，入資料在堆疊頂
出堆疊：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂
后進先出【類似于瀏覽器的回退，只會回傳上一個瀏覽后的頁面而不是回傳第一個打開的頁面；彈夾中的子彈】

邪惡的小技巧：合理的出堆疊順序（畫堆疊圖）
已知一個堆疊的入堆疊序列是m, n, x, y, z.則不可能出現的出堆疊順序是: C
A mnxyz
B xnyzm
C nymxz
D nmyzx

A

B

C

m要想出堆疊必須讓x出堆疊才行，所以是不可能的出堆疊順序

D

邪惡的小技巧：中綴運算式轉后綴運算式
有一個中綴運算式為a*(b-(c+d)),它的后綴運算式可以是什么: A
A abcd+-*
B abc+d-*
C ab-cd+*
D abd+c-*

前綴運算式: 把運算子放前邊
中綴運算式:a*(b-(c+d)
后綴運算式: 把運算子放后邊

按照運算優先級給運算子號放在括號外邊

a*(b-(c+d))確定優先級
(a*(b-(c+d))) 打括號
+ 先算
(a*(b- ( cd )+ ))移動符號
(a* ( b(cd)+ )- )
( a(b(cd)+)- )*
后綴運算式: abcd+-*

這樣就不用像第一題那樣每次都畫操作堆疊
方法總結：從左往右，根據運算子的優先級(注意括號問題)，額外加括號，把每個對應的運算子移到對應的括號外面，去除所有的括號，結果就是對應的前后綴運算式【后綴放后邊，前綴放前邊即可】

2*3(4+5)-6

(2*3(4+5)-6)
(2*3(45)+-6)
(2*(345)+*-6)
(2((345)+*)-6)
((2((345)+*))-6)
((2((345)+*))*6)-
2345 +**6-

應用
int func(后綴運算式)

1.2 實作

public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);// 增加元素
        stack.push(2);
        stack.push(3);
        System.out.println(stack.peek());// 獲取堆疊頂元素但不洗掉 3
        System.out.println(stack.pop());// 彈出堆疊頂元素 洗掉3
        System.out.println(stack.peek());// 獲取堆疊頂元素但不洗掉2
        System.out.println(stack.empty());// 堆疊自帶的 empty 方法
        System.out.println(stack.isEmpty());// 繼承 vector 的方法
        System.out.println(stack.search(2));// 查找下標
        System.out.println(stack.search(3));// 沒有就回傳 -1
    }

3
3
2
false
false
1
-1

Stack 原始碼

發現只有 push, peek, pop, empty, search 方法
為何可以使用 isEmpty 呢？

為何可以使用 isEmpty 方法呢，

因為 Stack 繼承 Vector，所以可以使用父類的 isEmpty方法
分析一下 push 壓堆疊操作，來查看它的底層是如何實作的

查看 addElementr 方法

如果不清楚源代碼內容的可以查看我的博客——List的使用中 add 方法一步步原始碼決議，了解堆疊的底層陣列如何擴容如何增加元素

我們查看一下 Stack 繼承和實作

發現這個體系是：Stack 類繼承 Veator 類, Vector 類繼承 AbstractList 類, AbstractList 類繼承自 AbstractCollection 類, AbstractCollection 類實作 Collection 介面, Collection 介面繼承 Iterable 介面

1.2.1 陣列實作Stack

import java.util.Arrays;

public class MyStackList<E> {
//    public static void main1(String[] args) {
//        Stack<Integer> stack = new Stack<>();
//        stack.push(1);// 增加元素
//        stack.push(2);
//        stack.push(3);
//        System.out.println(stack.peek());// 獲取堆疊頂元素但不洗掉 3
//        System.out.println(stack.pop());// 彈出堆疊頂元素 洗掉3
//        System.out.println(stack.peek());// 獲取堆疊頂元素但不洗掉2
//        System.out.println(stack.empty());// 堆疊自帶的 empty 方法
//        System.out.println(stack.isEmpty());// 繼承 vector 的方法
//        System.out.println(stack.search(2));// 查找下標
//        System.out.println(stack.search(3));// 沒有就回傳 -1
//    }

    private E[] elem;
    private int usedSize = 0;
    private int capacity = 4;

    MyStackList() {
        this.elem = (E[]) new Object[capacity];
    }

    // 擴容
    private void checkCapacity() {
        if (this.usedSize == this.capacity) {
            this.capacity *= 2;
            this.elem = Arrays.copyOf(this.elem, this.capacity);
        }
    }

    E push(E e) {
        checkCapacity();
        this.elem[this.usedSize++] = e;
        return this.elem[this.usedSize - 1];
    }

    E pop() {
        if (this.usedSize == 0) {
            throw new ArrayIndexOutOfBoundsException("Stack is empty !!!");
        } else {
            return this.elem[--this.usedSize];
        }
    }

    E peek() {
        if (this.usedSize == 0) {
            return null;
        } else {
            return this.elem[this.usedSize - 1];
        }
    }

    boolean empty() {
        return this.usedSize == 0;
    }

    void display() {
        for (int i = this.usedSize-1; i >= 0; i--) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

    private static void testPush() {
        MyStackList stack = new MyStackList();
        for (int i = 0; i < 10; i++) {
            System.out.print(stack.push(i) + " ");
        }
    }

    private static void testPop() {
        System.out.println("Push:");
        MyStackList stack = new MyStackList();
        for (int i = 0; i < 10; i++) {
            stack.push(i);
        }
        stack.display();

        System.out.println("Pop:");
        for (int i = 0; i < 15; i++) {
            System.out.print(stack.pop() + " ");
        }

        System.out.println("Residue: ");
        stack.display();
    }

    private static void testPeek() {
        MyStackList stack = new MyStackList();
        System.out.println("Push:");
        for (int i = 0; i < 10; i++) {
            stack.push(i);
        }
        stack.display();

        System.out.println("Peek:");
        for (int i = 5; i < 10; i++) {
            System.out.print(stack.peek() + " ");
        }

        System.out.println("Residue:");
        stack.display();
    }

    public static void main(String[] args) {
    	// 放置測驗用例
        testPop();
    }
}

陣列實作堆疊, 為了提高效率該如何插入洗掉資料呢？

1. 尾插尾刪: 避免了陣列元素的移動, 時間復雜度O(1)
2. 頭插頭刪: 還要移動資料, 時間復雜度O(N)

1.2.2 單鏈表實作Stack

class Node<E> {
    private E val;
    private Node next;

    public Node(E val) {
        this.val = val;
    }

    Node head;

    E push(E val) {
        Node node = new Node(val);
        if (head == null) {
            head = node;
            return (E) head.val;
        } else {
            node.next = head;
            head = node;
            return (E) head.val;
        }
    }

    E pop() {
        if (head == null) {
            throw new NullPointerException("NULL !!!");
        } else {
            E ret = (E) head.val;
            head = head.next;
            return ret;
        }
    }

    E peek() {
        if (head == null) {
            throw new NullPointerException("NULL !!!");
        } else {
            return (E) head.val;
        }
    }

    void display() {
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }
}

public class MyStackLinked<E> {
    private static void testPush() {
        Node node = new Node(null);
        for (int i = 0; i < 8; i++) {
            System.out.print(node.push(i) + " ");
        }
    }

    private static void testPop() {
        Node node = new Node(null);
        for (int i = 0; i < 8; i++) {
            node.push(i);
        }
        for (int i = 0; i < 5; i++) {
            System.out.print(node.pop() + " ");
        }
    }

    private static void testPeek() {
        Node node = new Node(null);
        for (int i = 0; i < 8; i++) {
            node.push(i);
        }
        for (int i = 0; i < 5; i++) {
            System.out.print(node.peek() + " ");
        }
    }

    public static void main(String[] args) {
        testPeek();
    }
}

單鏈表實作堆疊, 為了提高效率該如何插入洗掉資料呢？

1. 頭插頭刪: 時間復雜度O(1)
2. 尾插尾刪: 不帶尾節點單鏈表時間是復雜度O(N)；帶尾節點尾結點 tail 可以把入堆疊push操作的時間復雜度降到O(1)但是無法把出堆疊pop時間復雜度降到O(1)【需要找尾節點的前一個節點，所以是O(N)】

2. 佇列

2.1 概念

只允許一端進行資料插入操作，另一端進行資料洗掉操作的特殊線性表.佇列具有先進先出功能FIFO(First In First Out)
入佇列: 進行插入操作的一端稱為隊尾
出佇列: 進行洗掉操作的一端稱為對頭

先進先出【作業系統的程式點開執行順序，客服電話，鍵盤的輸入，記事本的輸出】

2.2 實作

發現 Queue 只有方框中的方法
Queue 介面繼承了 Collection 介面, Collection 介面繼承 Iterable 介面【實作程序比 Stack 簡單許多】

陣列實作Queue
陣列實作佇列有沒有什么問題呢？
因為是先進先出的, 所以會導致先出空間的內容造成浪費，而不是像堆疊那樣一直處于一端操作，不會造成空間浪費，如果元素移動的話來決解空間問題的話，時間復雜度會變為O(N)效率太低

因此陣列的話可以通過“回圈”的方式實作佇列
什么是“回圈佇列”呢？

分析解釋環形圖

1. 0~7: 陣列的參考
2. 11, 12, 13, 14, 15, 16, 17存盤的元素值
3. rear：指向插入元素的參考【帶插入元素的下一個索引】，圖中代表的是剛插入元素17還未移動rear下標，此時插入元素操作完畢后的rear應該移動到下一個索引0處
4. front：指向對頭元素的索引，每次出佇列一個元素就移動一次front

思考: 何時代表佇列滿了, 何時代表佇列空?

1. 當 front==rear 的時候，有兩種可能: 要么佇列滿要么佇列空
2. 如果 rear 的下一個是 front 就代表滿了【現在可以區front==rear】的兩種情況了

思考: rear走到陣列末尾，該如何跳轉到陣列0下標開頭呢?

最簡單的方法就是 if 判斷

if (re a r== elem.length-1){// 走到了隊尾
	rear = 0;
}

這時候如果利用取余運算呢? 會發現有不同的運算效果
假設一邊有插入一邊有洗掉，那么這個時候即可實作回圈操作對立達到堆空間的利用的同時復雜度還是O(1)

2.2.1 陣列實作回圈佇列

這是一個 OJ 鏈接
方案1會浪費一個位置的佇列空間，代碼如下：

class MyCircularQueue {
    private int[] elem;
    private int front, rear;

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


    /**
     * 入佇列
     *
     * @param value 值
     * @return
     */
    public boolean enQueue(int value) {
        if ((this.rear + 1) % this.elem.length == this.front) {
            return false;//滿了
        } else {
            this.elem[this.rear] = value;
            this.rear = (this.rear + 1) % this.elem.length;
            return true;
        }
    }

    /**
     * 出佇列
     *
     * @return
     */
    public boolean deQueue() {
        if (this.front == this.rear) {
            return false;
        } else {
            int val = this.elem[this.front];
//            this.front = (this.front + 1) % this.elem.length;// 因為是回圈，所以不能直接 front+1
            return true;
        }
    }

    /**
     * 取隊頭元素【相當于 peek 】
     *
     * @return
     */
    public int Front() {
        if (this.front == this.rear) {
            return -1;// leetcode 拋例外會認為是你的代碼錯誤，所以不能拋例外
        } else {
            int val = this.elem[this.front];
            return val;
        }
    }

    /**
     * 取隊尾元素
     * rear處于0位置則回傳this.elem.length-1
     * 所以不能直接進行 -1 操作
     *
     * @return
     */
    public int Rear() {
        if (this.rear == this.front) {
            return -1;
        } else {
            if (this.rear == 0) {
                return this.elem[this.elem.length - 1];
            } else {
                return this.elem[this.rear - 1];
            }
        }
    }

    public boolean isEmpty() {
        return this.front == this.rear;
    }

    public boolean isFull() {
        return this.rear + 1 == this.front;
    }
}

方案2，通過一個額外的變數來記錄佇列的狀態【并非 OJ 題目代碼，只是提供一個思路，把最后的佇列空間利用完】

public class my_Queue_list<E> {
    E[] elem = (E[]) new Object[5];
    // 佇列有效區間[head, tail)
    private int head = 0;
    private int tail = 0;
    private int size = 0;

    // 1.入佇列
    boolean offer(E val) {
        if (size == elem.length) {
            return false;
        } else {
            elem[tail++] = val;
            tail = tail % elem.length;
            ++size;
            return true;
        }
    }

    // 2.出佇列
    E poll() {
        if (size == 0) {
            return null;
        } else {
            E ret = (E) elem[head++];
            head = head % elem.length;
            --size;
            return ret;
        }
    }

    // 3.取隊首元素
    E peek() {
        if (size == 0) {
            return null;
        } else {
            return (E) elem[head];
        }
    }

    // 4.列印
    void display() {
        for (int i = 0; i < size; i++) {
            System.out.print(elem[i] + " ");
        }
    }

    private static void test_offer() {
        my_Queue_list my_queue_list = new my_Queue_list();
        for (int i = 0; i < 5; i++) {
            my_queue_list.offer(Integer.valueOf(i));
        }
        my_queue_list.display();
    }

    private static void test_poll() {
        my_Queue_list my_queue_list = new my_Queue_list();
        for (int i = 0; i < 5; i++) {
            my_queue_list.offer(Integer.valueOf(i));
        }
        for (int i = 0; i < 5; i++) {
            System.out.print(my_queue_list.poll() + " ");
        }
    }

    private static void test_peek() {
        my_Queue_list my_queue_list = new my_Queue_list();
        for (int i = 0; i < 5; i++) {
            my_queue_list.offer(Integer.valueOf(i));
        }
        System.out.println(my_queue_list.peek());
    }

    public static void main(String[] args) {
    	// 放置測驗用例
        test_peek();
    }
}

2.2.2 單鏈表實作Queue

class Node<E>{
    private E val;
    private Node next;
    private int usedSize;

    public Node(E val) {
        this.val = val;
        this.usedSize = 0;
    }
    Node front;
    Node rear;

    /**
     * 入佇列
     * @param val 值
     * @return
     */
    E offer(E val){
        Node node = new Node(val);
        if (this.front == null){
            this.front = node;
            this.rear = node;
        }else{
            this.rear.next = node;
            this.rear = node;
        }
        ++this.usedSize;
        return (E) this.rear.val;
    }

    /**
     * 出佇列
     * @return
     */
    E poll(){
        if (this.front == null){
            throw new NullPointerException("Queue is empty !!!");
        }else{
            E ret = (E) this.front.val;
            if (this.front.next == null){
                this.front = null;
                this.rear = null;
            }else{
                this.front = this.front.next;
            }
            --this.usedSize;
            return ret;
        }
    }

    /**
     * 出對頭元素但不洗掉
     * @return
     */
    E peek(){
        if (this.front == null){
            throw new NullPointerException("Queue is empty !!!");
        }else{
            E ret = (E) this.front.val;
            return ret;
        }
    }

    /**
     * 為空
     * @return
     */
    boolean isEmpty(){
        return this.usedSize == 0;
    }

    /**
     * 佇列長度
     * @return
     */
    int size(){
        return this.usedSize;
    }
}
public class MyQueueLinked {
    private static void tstOffer(){
        Node node = new Node(null);
        for (int i = 0; i < 8; i++) {
            System.out.print(node.offer(i) + " ");
        }
    }

    private static void testPoll(){
        Node node = new Node(null);
        for (int i = 0; i < 8; i++) {
            node.offer(i);
        }
        for (int i = 0; i < 9; i++) {
            System.out.print(node.poll()+" ");
        }
    }

    private static void testPeek(){
        Node node = new Node(null);
        for (int i = 0; i < 8; i++) {
            node.offer(i);
        }
        for (int i = 0; i < 9; i++) {
            System.out.print(node.peek()+" ");
        }
    }
    public static void main(String[] args) {
    	// 放置測驗用例
        testPeek();
    }
}

3. Stack 和 Queue 常用 API 總結

Stack

Queue

4. 結尾語

兩堆疊共享空間這種操作我還不會，以后會學會了會繼續更新堆疊內容
堆疊和佇列說簡單也簡單，說難也有一絲的難度，
下面是我的感悟：
人生，就像是一個很大的堆疊演變，
自下而上的增長，不僅僅是自然萬物，也是我們的成長經歷程序，
從出生時我們赤裸裸的來到這個世間，漸漸地長大，知道我們變老，經歷的周圍人的生老病死，最終我們還的赤裸裸地衣蕉訓“鄉”，

人生，又放佛是一天一天小小的堆疊重現，
呀呀學語的時候，父母每天為抱著我們不斷的進出家門，青少年的時候有叛逆，青年的時候高中和大學的接軌，是否和父母一樣保持著童年時期的聯系，壯年時候將會奔波于家和事業之間，老年了，我想我會小園香徑獨徘徊于養老院門里屋前，

人生，更需要有堆疊的精神體現，
在哪里跌倒就在哪里爬起，無論是否見到堆疊底，我們始終應該保持堆疊定的仰望天空，只要有希望，不斷進取，出頭之日將會重現，困難不會永遠存在，強者才會勇往直前，

人生，其實就是一個大大的佇列演變，
無知童年，快樂少年，稚嫩青年，成熟中年，安逸晚年，

人生，也是一個又一個小小的佇列重現，
春夏秋冬輪回年年，早中晚夜回圈天天，變化的是時間，不變的是對未來執著的信念，

人生，更需要有佇列精神的體現，
南極到北極，不過時南緯 90 度到北緯 90 度的佇列，如果中途猶豫，臨時轉向，也許只能與企鵝或北極熊相伴，可事實是無論堅持哪個方向，你都會到達終點，

大部分人都是普通人，學習資料結構，我很笨，想著宏偉的計劃，卻發現別人學一遍的我需要兩遍才能弄明白，佇列精神對于普通人來說，已經很寶貴，聰明人可以轉向，繞過許多溝壑以最快的速度到達終點，但是普通人只能腳踏實地的一步一個腳印走完該走的路，