棧的概念

棧是一種先進后出的線性表，只允許在固定的一端進行插入和刪除操作。
進行插入和刪除操作的一端被稱為棧頂，另一端被稱為棧底

棧的插入操作叫做進棧/壓棧/入棧
棧的刪除操作叫做出棧

現實生活中棧的例子：

棧的模擬實現

下面是Java集合類給我們提供的棧的方法：

模擬實現順序棧

我們通過數組來模擬實現棧。

構建數組棧

我們需要兩個成員變量，一個是數組，另一個是記錄當前的數據個數。

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

push

要考慮擴容問題

    private boolean isFull() {if(usedSize == elem.length) {return true;}return false;}private void grow() {elem = Arrays.copyOf(elem,2*elem.length);}public void push(int val) {if(isFull()) {grow();}elem[usedSize++] = val;}

isEmpty

判斷棧是否為空：

    public boolean isEmpty() {return usedSize == 0;}

pop

設置自定義異常：

public class PopException extends RuntimeException{public PopException() {super();}public PopException(String message) {super(message);}
}

刪除棧頂的同時，還會返回刪除的元素：

    private void checkPop() throws PopException{if(isEmpty()) {//拋異常throw new PopException("棧已空，無法刪除！！！");}}public int pop() {try {checkPop();int ret = elem[usedSize-1];usedSize--;return ret;} catch (PopException e) {e.printStackTrace();}return -1;}

peek

獲取棧頂元素 但是不刪除

    public int peek() {try {checkPop();return elem[usedSize-1];} catch (PopException e) {e.printStackTrace();}return -1;}

鏈式棧

鏈式棧顧名思義就是利用鏈表來保存棧

假設使用單鏈表制作鏈式棧，建議使用頭插和頭刪法來進行push和pop操作，peak直接把頭節點的值獲取即可，這樣時間復雜度可以為O（1）；但是如果你使用尾插和尾刪就是以尾節點的位置作為棧頂，在push，pop 和 peak 的時候，時間復雜度為O（N）

假設使用雙向無頭循環鏈表，無論是選擇頭插頭刪還是尾插尾刪作為push與pop，時間復雜度都是O（1）

這里就不演示鏈式棧的代碼。

Stack 的使用

push 入棧；pop 出棧；peak 獲取棧頂元素；empty 是否為空；size 這個獲取有效元素的方法是在Vector 中的，search 找到某元素距離棧頂元素的距離多少（棧頂元素記為1，然后一直到目標元素）

棧、虛擬機棧、棧幀有什么區別呢？

棧是我們的數據結構的其中一種形式，虛擬機棧是JVM虛擬機的一塊內存，棧幀是運行一個方法或者函數的時候計算機給它開辟的內存。

隊列的概念

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

隊列類似我們生活中的排隊。

隊列的模擬實現

上面是Java集合類給我們提供的隊列的方法，其中add和offer都是入隊操作，poll 和 remove 都是出隊操作，element 和 peek 都是獲取隊列頭部的元素。

它們主要的區別是會不會拋異常~~ 下面有詳細的介紹：

---

鏈式隊列

這里我們將使用數組來模擬實現隊列，并且這里只實現下圖所示的方法：

size 和 isEmpty 是隊列繼承的方法，并且隊列沒有重寫這兩個方法，所以上面的IDEA直接看隊列的Structure 是看不到的。

---

假設我們使用單鏈表為基礎，該怎么實現隊列？
假設入隊采用尾插，那要出隊即使用頭刪即可
出隊列使用單鏈表的頭刪即可，時間復雜度為O（1）
入隊列使用尾插，一般情況下，單鏈表實現尾插首先要找到尾，然后才是開始插入，這時候時間復雜度就尾O（N），不是最優解，我們可以加一個尾指針保存好尾節點，這樣就方便我們快速進行尾插操作。

假設入隊使用頭插，那出隊的時候就需要使用尾刪
這時候就不好弄了，即使你有尾指針在進行尾刪的時候還是需要遍歷鏈表找到尾節點的前一個結點才能完成尾刪，這時候你可能會認為再定義一個指針，這就很麻煩了。

所以單鏈表構建隊列的話，限制條件有點大，但是使用上一片文章的雙向鏈表（無頭雙向循環鏈表 LinkedList） ，就可以隨意選取一端作為入隊，另一端作為出隊。

這里我們入隊采用尾插，出隊采用頭刪：

public class MyQueue {public static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//入隊public boolean offer(int data) {ListNode node = new ListNode(data);if(isEmpty()) {last = head = node;} else {last.next = node;node.prev = last;last = node;}return true;}public boolean isEmpty() {return head == null;}//出隊public int poll() {if(isEmpty()) {return -1;}int ret = head.val;if(head.next != null) {head.next.prev = null;}head = head.next;return ret;}//求結點個數public int size() {ListNode cur = head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}//獲取隊頭元素public int peek() {if(isEmpty()) {return -1;}return head.val;}
}

這里要注意出隊的代碼，如果只有一個結點的情況下，你進行刪除后就沒有結點了，head.next.prev = null 這行代碼就會發生報錯。

順序隊列

順序隊列我們采用數組來實現隊列，這時候我們就要思考一個問題，在不斷的出隊入隊的情況下怎么保證空間盡可能地利用起來？
假設數組的數據已滿裝滿的情況下，我們一直出隊直到數組變空的話，怎么利用起來前面的空間？

循環隊列

這時候我們就需要使用循環隊列讓隊列的空間有效的利用起來。

法1 ：定義一個成員變量，usedSize 記錄使用了多少的空間
法2 ： 定義一個標記符，記錄空間是否已滿
法3 ：浪費一個空間，通過數學公式判斷隊列是否已滿

一般情況下，我們會認為這就是隊列空和滿的兩種狀態，但是這兩種狀態都是 front == near，怎么辦？
根據法1，我們可以記錄使用了多少空間的usedSize 來判斷隊列是否已滿，即 usedSize = 數組的長度即可認為隊列已滿
根據法2，我們使用標記符，首先 將標記符記為 -1，認為隊列沒滿，當front 與near 再次相遇時，標記符乘 -1 變為1 ，判斷 隊列 已滿，如果下一個操作時出隊，那標記符再自乘 -1變回 -1 ，當front 與 rear 再次相遇時標記符自乘 -1 變為1 表示隊列已滿，以此類推，這里大家可以自由發揮。

---

第三個方法是利用隊列自身來進行判斷，當 rear 的下一個就是 front 的時候（即 ( rear + 1 ) % 數組長度 == front），就判斷隊列已滿，這需要我們浪費隊列的一個空間。

---

如何讓rear 和 front 循環起來呢？即rear 的下標該如何制定呢？
這里有一個公式，當 rear 要 自增的時候，新的 rear = ( rear + 1 ) % 數組長度就是此時rear 對應的實際下標，當 rear 為 7 時，rear 向下移動一格時，新的 rear 就是 ( 7 + 1 ) % 8 = 0， 正好就是 7 下一個的下標值 0

---

問題拓展 （數組下標循環的小技巧）

下標往后移動(o?set 小于 array.length): index = (index + o?set) % array.length

---

下標往前移動(o?set 小于 array.length): index = (index + array.length - o?set) % array.length

array.length - o?set 其實就是變相地讓 小標變成向后 移動。

---

順序隊列的代碼

public class MyQueue {int front;int rear;int[] elem;public MyQueue() {elem = new int[4];}//入隊public boolean offer(int data) {if(isFull()) {return false;}elem[rear] = data;rear = (rear + 1) % elem.length;return true;}//隊列是否已滿private boolean isFull() {return (rear + 1) % elem.length == front;}//隊列是否為空public boolean isEmpty() {return rear == front;}//出隊public int poll() {if(isEmpty()) {return -1;}int ret = elem[front];front = (front + 1) % elem.length;return ret;}//求元素個數public int size() {int count = 0;for (int i = front; i < rear; i++) {count++;}return count;}//獲取隊頭元素public int peek() {if(isEmpty()) {return -1;}return elem[front];}
}

Queue

上面是我們常用的隊列方法

隊列Queue本質上是一個接口，所以Queue 不能被實例化，那如何使用？

Deque （雙端隊列）

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

我們可以發現 Deque 其實是繼承了 Queue 接口，但是還是一個接口，還是不能實例化，那怎么使用？請看下面解說。

LinkedList 和棧與隊列的關系

LinkedList 有很多接口其中包括了 Deque ，而Deque 這個接口其實繼承了 Queue ，也就是隊列，所以我們可以實例化 一個LinkedList 對象然后通過 Queue 接收就可以使用普通隊列的方法，同理，通過實例化一個LinkedList 對象然后通過 Deque 接收就可以使用雙端隊列的方法

---

    public static void main(String[] args) {LinkedList<Integer> linkedList = new LinkedList<>();linkedList.push(1);linkedList.push(2);linkedList.push(3);System.out.println(linkedList.peek());System.out.println(linkedList.pop());System.out.println(linkedList.peek());}

LinkedList還可以當成棧來使用，也就是說LinkedList還包含棧的方法，自身功能很強大。

小結：
LinkedList 不僅可以作為不帶頭的雙向循環鏈表使用，還可以當成棧或者隊列使用。

---

在實際工程中，使用Deque接口是比較多的，棧和隊列均可以使用該接口。

Deque<Integer> stack = new ArrayDeque<>();//雙端隊列的線性實現
Deque<Integer> queue = new LinkedList<>();//雙端隊列的鏈式實現

---

習題鏈接：
http://t.csdnimg.cn/aV91m