棧和隊列

1. 棧（Stack）
1. 棧的應用一：方法的系統(tǒng)調用棧
2. 棧的應用二：前進后退功能
3. 棧的代碼實現(xiàn)：分別使用數(shù)組和鏈表實現(xiàn)
   
2. 隊列（Queue）
1. 使用數(shù)組實現(xiàn)隊列
2. 使用單向鏈表實現(xiàn)隊列
3. 優(yōu)化單向鏈表實現(xiàn)的隊列
4. 優(yōu)化數(shù)組實現(xiàn)的隊列：循環(huán)隊列
   

• 元素進棧的順序是：34、21、66
• 元素出棧的順序是：66、21、34

1. 棧頂：可以操作數(shù)據(jù)的一端稱為棧頂
2. 棧底：不可以操作數(shù)據(jù)的一端稱為棧底

public static void main(String[] args) {     a(10);}
public static int a(int x) {    int y = b(x, 1);    return y;}
public static int b(int x, int y) {    int sum = x + y;    c(sum);    return sum;}
public static void c(int x) {    System.out.println(x);}

1. 首先使用棧來記錄每一個操作，用戶每操作過一次就將操作壓入棧中
2. 等用戶想返回的時候，只需要將操作出棧即可

• 當用戶需要后退的時候，將第一個棧中的棧頂操作出棧，然后將出棧的操作再次壓入到第二個棧中
• 當用戶需要前進的時候，將第二個棧中的棧頂操作出棧，然后將出棧的操作再次壓入到第一個棧中

1. push 操作：向棧中壓入元素

2. pop 操作：從棧中彈出棧頂元素
   

1. push 操作：向數(shù)組的末尾追加元素，這個操作的時間復雜度是 O(1)

2. pop 操作：將數(shù)組末尾的元素刪除掉，注意，這里并不要真的刪除末端元素，而是直接將 size-- 即可，這樣可以實現(xiàn)常量級別的時間復雜度

在使用單向鏈表來實現(xiàn)棧的時候，我們只對鏈表的表頭進行操作：

1. push 操作：向單向鏈表表頭插入元素，這個操作是常量級別的時間復雜度

2. pop 操作：將單向鏈表的表頭刪除，這個操作也是常量級別的時間復雜度

可以看出，不管是使用數(shù)組還是單向鏈表實現(xiàn)棧，push 和 pop 的時間復雜度都是 O(1)

注意：代碼實現(xiàn)請見視頻講解

隊列 (Queue)

• 從一端將數(shù)據(jù)添加到隊列中，這個過程我們稱為入隊 (enqueue)
• 從另一端將數(shù)據(jù)從隊列中刪除，這個過程我們稱為出隊 (dequeue)

和棧一樣，隊列可以使用數(shù)組、也可以使用鏈表來實現(xiàn)。

1. 到底使用靜態(tài)數(shù)組還是動態(tài)數(shù)組，這要看實現(xiàn)的隊列是固定容量的還是動態(tài)容量的，我們這里先實現(xiàn)一個動態(tài)容量的隊列，所以使用動態(tài)數(shù)組來實現(xiàn)
2. 到底使用數(shù)組的哪一端作為隊首，哪一端作為隊尾，我們看下面的分析

• 入隊的操作就是 addFirst，它的時間復雜度是 O(n)
• 出隊的操作就是 removeLast，它的時間復雜度是 O(1)

• 入隊的操作就是 addLast，它的時間復雜度是 O(1)
• 出隊的操作就是 removeFirst，它的時間復雜度是 O(n)

所以說。不管選哪個端作為隊首，時間復雜度都是一樣的，都會有一個操作是 O(n)，一個是 O(1)，所以選哪一端作為隊首都一樣

注意：代碼實現(xiàn)請見視頻講解

二、使用單向鏈表實現(xiàn)隊列

• 入隊的操作就是 addFirst，它的時間復雜度是 O(1)
• 出隊的操作就是 removeLast，它的時間復雜度是 O(n)

• 入隊的操作就是 addLast，它的時間復雜度是 O(n)
• 出隊的操作就是 removeFirst，它的時間復雜度是 O(1)

注意：代碼實現(xiàn)請見視頻講解

我們使用單向鏈表實現(xiàn)了隊列，不管是以鏈表的哪一端作為隊首，隊列中的出隊和入隊兩個操作肯定會有一個操作的時間復雜度是 O(n)，我們能不能將這個時間復雜度降為 O(1) 呢？

我們要優(yōu)化時間復雜度，先要找到導致時間復雜度高的原因，我們先看看下面的兩張圖：

所以，我們要降低單向鏈表實現(xiàn)的隊列出隊入隊的時間復雜度，那么就要降低對單向鏈表最后一個節(jié)點操作的時間復雜度。

我們現(xiàn)在回想下，為什么對單向鏈表的頭不管是刪除還是新增操作的時間復雜度是 O(1) 呢？答案就是我們通過一個變量 head 記住了鏈表頭節(jié)點的位置，所以對頭的操作的時間復雜度可以為常量級別

借助這個方法，我們也可以使用一個變量 tail 來記住單向鏈表的尾節(jié)點，看看能不能降低對尾節(jié)點的操作時間復雜度呢？

1. removeLast 操作的時間復雜度還是 O(n)，之所以時間復雜度沒有變化，是因為要刪除最后一個節(jié)點，就需要找到最后一個節(jié)點的前一個節(jié)點，然而對于單向鏈表，要找到最后一個節(jié)點的前一個節(jié)點需要從頭節(jié)點開始遍歷找到，所以時間復雜度還是 O(n)
2. addLast 操作的時間復雜度變成了 O(1)，這個是因為在最后一個節(jié)點后面新增一個節(jié)點，只需要知道最后一個節(jié)點的位置即可，然而我們已經(jīng)使用 tail 變量記錄了最后一個節(jié)點的位置了。

從上圖，我們也可以得出一個結論：要使得單向鏈表實現(xiàn)的隊列的出隊和入隊操作的時間復雜度都是 O(1) 的話，那么必須使用單向鏈表表頭做隊首。

以上，我們是使用單向鏈表 + 表頭表尾兩個指針來實現(xiàn)隊列，而且實現(xiàn)的出隊和入隊的時間復雜度都是 O(1)

當然，你完全可以使用雙向鏈表來實現(xiàn)隊列，這樣出隊和入隊的時間復雜度也是 O(1)

但是直接使用雙向鏈表實現(xiàn)的隊列，比使用單向鏈表 + 表頭表尾兩個指針實現(xiàn)的隊列更加的耗費空間，因為雙向鏈表的每個節(jié)點都多了一個前置指針

注意：代碼實現(xiàn)請見視頻講解

四、循環(huán)隊列

前面我們對使用單向鏈表實現(xiàn)的隊列進行了優(yōu)化，使得出隊和入隊的時間復雜度都是 O(1)

那么，我們能不能對數(shù)組實現(xiàn)的隊列也進行優(yōu)化呢？答案是可以的，那就是接下來要講解的循環(huán)隊列了

當?shù)谝粋€元素出隊了，我們不需要移動剩下的元素，而是直接將 head 往后移動一位，如下：

• 什么時候表示隊列為空
• 什么時候表示隊列已經(jīng)滿了

在實現(xiàn)循環(huán)隊列之前，我們還有一個問題需要解決：head 和 tail 是怎么移動的？每次移動都 +1 嗎？這樣的話，head 和 tail 肯定會超出數(shù)據(jù)界限的，我們可以使用取模的手段，將 head 和 tail 控制在數(shù)組范圍內，如下：

head = (head + 1) % data.length tail = (tail + 1) % data.length

注意：代碼實現(xiàn)講解請見視頻講解

package com.douma.line.queue;
/** * @微信公眾號 : 抖碼課堂 * @官方微信號 : bigdatatang01 * @作者 : 老湯 */public class LoopQueue<E> implements Queue<E> {    private E[] data;    private int head;    private int tail;
    private int size;
    public LoopQueue() {        this(20);    }
    public LoopQueue(int capacity) {        data = (E[])new Object[capacity];        head = tail = 0;        size = 0;    }
    // 當前隊列的容量    public int getCapacity() {        return data.length - 1;    }
    @Override    public int getSize() {        return size;    }
    @Override    public void enqueue(E e) {        if ((tail + 1) % data.length == head) {            // 隊列滿了            resize(getCapacity() * 2);        }        data[tail] = e;        size++;        tail = (tail + 1) % data.length;    }
    @Override    public E dequeue() { // O(1)        if (isEmpty()) {            throw new RuntimeException("dequeue error, No Element for dequeue");        }        E res = data[head];        data[head] = null;        size--;        head = (head + 1) % data.length;        if (size == getCapacity() / 4) {            resize(getCapacity() / 2);        }        return res;    }
    private void resize(int newCapacity) {        E[] newData = (E[])new Object[newCapacity + 1];        for (int i = 0; i < size; i++) {            newData[i] = data[(i + head) % data.length];        }        data = newData;        head = 0;        tail = size;    }
    @Override    public E getFront() {        return data[head];    }
    @Override    public boolean isEmpty() {        return head == tail;    }
    @Override    public String toString() {        StringBuilder sb = new StringBuilder();        sb.append(String.format("Queue：size = %d, capacity = %d\n", size, getCapacity()));        sb.append(" 隊首 [");        for (int i = head; i != tail ; i = (i + 1) % data.length) {            sb.append(data[i]);            if ((i + 1) % data.length != tail) {                sb.append(",");            }        }        sb.append("]");        return sb.toString();    }}

碼字不易，點贊、看一看兩連即可。