棧（stack）是限定僅在表尾進行插入和刪除操作的線性表。
隊列（queue）是一種先進先出（First In First Out）的線性表。

一、棧

1.棧的定義

• 棧頂：允許插入和刪除的一端為棧頂

• 棧底：另一端

棧是一種后進先出（Last In First Out）的線性表，簡稱 LIFO 結構。既然棧是一種只允許在尾端進行刪除操作的線性表，那么線性表的特性它全部都有。根據(jù)存儲結構的不同，?？梢苑殖桑喉樞驐：玩湕?。

2.順序棧

順序棧其實就是一個數(shù)組，只不過需要在聲明的時候就確定長度。當頭指針 top 指向 -1 的時候，表示空棧。一般將頭指針 top 指向尾端的元素。

• 進棧：需要注意棧是否已經(jīng)滿了（top == MAX_SIZE - 1）,如果不滿，則壓入棧，同時 top 指針加一。

• 出棧：需要注意棧是否為空棧（top == - 1）,如果不空，則出棧，同時 top 指針減一。

時間復雜度均為 O(1)。

3.鏈棧

棧的鏈式存儲結構，其實就是單鏈表，只不過它的頭指針不再指向頭結點，而是指向最尾的節(jié)點（棧頂元素）。

• 進棧：將新節(jié)點的 next 指針指向 top，然后將 top 指針指向當前的新節(jié)點，鏈表數(shù)量加一。

• 出棧：保存尾節(jié)點，將 top 指針指向 top.next，釋放剛剛的尾節(jié)點，鏈表數(shù)量減一。

時間復雜度均為 O(1)。

4.用途

Java 對棧（Stack）進行了封裝，可以直接使用，棧一般用作函數(shù)調(diào)用?；蛘?Activity 棧。

對于函數(shù)調(diào)用棧，在前行階段，對于每一層遞歸，函數(shù)的局部變量、參數(shù)值以及返回地址都被壓入棧中。在退回階段，位于棧頂?shù)木植孔兞俊?shù)值和返回地址被彈出，用于返回調(diào)用層次中執(zhí)行代碼的其余部分，也就是恢復了調(diào)用的狀態(tài)。

5.棧的面試題

• 劍指 Offer 面試題 21：定義棧的數(shù)據(jù)結構，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min() 函數(shù)。在該棧中，調(diào)用min()，push() 及 pop() 的時間復雜度都是 O(1)。

  思路：建立一個數(shù)據(jù)棧和輔助棧，輔助棧的棧頂每次壓入數(shù)據(jù)棧棧頂和輔助棧棧頂兩個元素中的最小值，這樣當彈出一個數(shù)據(jù)棧的時候，對應彈出一個輔助棧，因為兩者已經(jīng)關聯(lián)過大小了，所以當下一次獲取最小值的時候必然跟上次已經(jīng)彈出的元素無關。如果想要獲取最小的元素，直接彈出輔助棧的棧頂即可。

show my code

public class MinStack {
    
    //數(shù)據(jù)棧
    private Stack<Integer> data = new Stack<>();
    //輔助棧
    private Stack<Integer> min = new Stack<>();
    
    /**
     * 壓棧
     * @param i
     */
    public void add(Integer item) {
        //數(shù)據(jù)棧直接入棧
        data.push(item);
        
        //輔助棧需要判斷，確保入棧的是最小的元素
        if(min.isEmpty() || item <= min.peek()) {
            min.push(item);
        }else {
            min.push(min.peek());
        }
    }
    
    /**
     * 出棧
     * @return
     */
    public Integer pop() {
        if(data.isEmpty() || min.isEmpty()) {
            return -1;
        }
        
        //彈出輔助棧的棧頂
        min.pop();
        
        //彈出數(shù)據(jù)棧棧頂
        return data.pop();
    }
    
    /**
     * 獲取棧最小的元素
     * @return
     */
    public Integer min() {
        if(data.isEmpty() || min.isEmpty()) {
            return 0;
        }
        
        //直接彈出輔助棧的棧頂
        return min.peek();
        
    }
    
    /**
     * 打印棧
     */
    public void printStack() {
        System.out.print("棧元素: ");
        for(Integer i:data) {
            System.out.print(i+" ");
        }
        System.out.println("");
        System.out.println("*************************");
    }
    
}

測試過程及結果

public static void main(String[] args) {  
        MinStack stack = new MinStack();
        stack.add(10);
        stack.add(999);
        stack.add(23);
        stack.add(654);
       
        stack.printStack();
        
        System.out.println("出棧元素："+stack.pop());
        stack.printStack();
        
        
        System.out.println("Min 元素："+stack.min());
        stack.printStack();
    }

MinStack

• 劍指 Offer 面試題 22：題目：輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷二個序列是否為該棧的彈出順序。假設壓入棧的所有數(shù)字均不相等。

思路：解決這個問題很直觀的想法就是建立一個輔助棧，把輸入的第一個序列中的數(shù)字依次壓入該輔助棧，并按照第二個序列的順序依次從該棧中彈出數(shù)字。

判斷一個序列是不是棧的彈出序列的規(guī)律：如果下一個彈出的數(shù)字剛好是棧頂數(shù)字，那么直接彈出。如果下一個彈出的數(shù)字不在棧頂，我們把壓棧序列中還沒有入棧的數(shù)字壓入輔助棧，直到把下一個需要彈出的數(shù)字壓入棧頂為止。如果所有的數(shù)字都壓入棧了仍然沒有找到下一個彈出的數(shù)字，那么該序列不可能是一個彈出序列。

show my code

/**
     * 檢測一個棧的出棧順序是否存在
     * @param push 數(shù)字的入棧順序
     * @param pop  數(shù)字的出棧順序
     * @return
     */
    public static boolean verifyStackPopOrder(int push[],int pop[]){
        
        //驗證輸入數(shù)據(jù)是否合法，壓棧和出棧的數(shù)組的長度必須一致
        if(push == null || pop == null || push.length == 0 || pop.length == 0
                || push.length != pop.length){
            System.out.println("輸入數(shù)據(jù)不合法");
            return false;
        }
        
        //構造輔助棧，作為數(shù)據(jù)棧
        Stack<Integer> data = new Stack<>();
        //壓棧數(shù)組的壓入位置
        int pushIndex = 0;
        //出棧數(shù)組的出棧位置
        int popIndex = 0;
        
        //遍歷出棧的數(shù)組，假如發(fā)現(xiàn)出棧的數(shù)據(jù)和壓棧的棧頂元素相同，就將壓棧數(shù)據(jù)的棧頂元素彈出，否則一直壓入，
        //直到壓棧元素和出棧的棧頂元素相等，彈出壓棧的棧頂元素，然后處理下一個出棧的棧頂元素
        
        //未處理完出棧的數(shù)組
        while(popIndex < pop.length){
            
            //根據(jù)一個出棧的棧頂元素，遍歷入棧的數(shù)組，直到找到相等的元素 或者全部已經(jīng)入棧
            while(pushIndex < push.length && (data.isEmpty() || data.peek() != pop[popIndex])){
                //壓數(shù)據(jù)進去數(shù)據(jù)棧
                data.push(push[pushIndex]);
                pushIndex ++;
            }
            
            //出棧棧頂元素找到和入棧的棧頂元素相同的，數(shù)據(jù)棧棧頂元素出棧，繼續(xù)處理下一個出棧元素
            if(data.peek() == pop[popIndex]){
                data.pop();
                popIndex ++;
                //如果出棧順序正確，那么所有數(shù)據(jù)棧元素都會被出棧，數(shù)據(jù)棧最后會變?yōu)榭盏臈?            }else {
                //全部已經(jīng)壓入棧，但是找不到和出棧棧頂元素相等的
                return false;
            }
            
        }
        
        //假如能運行到這里說明，已經(jīng)全部壓入棧，而且出棧的元素也已經(jīng)全部彈出，說明順序是正確的,這個肯定是true
        return data.isEmpty();
    }

測試過程及結果

public static void main(String[] args){  
        int[] push = {1, 2, 3, 4, 5};
        int[] pop1 = {4, 5, 3, 2, 1};
        int[] pop2 = {3, 5, 4, 2, 1};
        int[] pop3 = {4, 3, 5, 1, 2};
        int[] pop4 = {3, 5, 4, 1, 2};

        System.out.println("人工計算為true，程序得出的出棧順序為: " + verifyStackPopOrder(push, pop1));
        System.out.println("人工計算為true，程序得出的出棧順序為: " + verifyStackPopOrder(push, pop2));
        System.out.println("人工計算為false，程序得出的出棧順序為: " + verifyStackPopOrder(push, pop3));
        System.out.println("人工計算為false，程序得出的出棧順序為: " + verifyStackPopOrder(push, pop4));
        
        int[] push5 = {1};
        int[] pop5 = {2};
        System.out.println("人工計算為false，程序得出的出棧順序為: " + verifyStackPopOrder(push5, pop5));

        int[] push6 = {1};
        int[] pop6 = {1};
        System.out.println("人工計算為true，程序得出的出棧順序為: " + verifyStackPopOrder(push6, pop6));

        System.out.println("人工計算為false，程序得出的出棧順序為: " + verifyStackPopOrder(null, null));
    }

驗證出棧順序

二、隊列

1.隊列的定義

• 隊頭：允許刪除的一端

• 隊尾：允許插入的一端

隊列是一種特殊的線性表，所以隊列也是具有順序存儲結構和鏈式存儲結構的。

2.隊列的順序存儲結構（循環(huán)隊列）

為了解決用數(shù)組來實現(xiàn)隊列的“假溢出”問題，我們一般將順序存儲結構的隊列頭尾相接，這種把隊列的頭尾相接的順序存儲結構稱為循環(huán)隊列。

int front;  // 頭指針
int rear； // 尾指針

• 隊列滿的條件：(rear+1) % QueueSize == front

• 計算隊列長度公式：length = （rear - front + QueueSize）% QueueSize

3.隊列的鏈式存儲結構（鏈隊列）

隊列的鏈式結構其實就是鏈表，只是有頭指針和尾指針。當隊列為空的時候，頭指針和尾指針都指向頭結點。

Node front;  // 頭指針
Node rear； // 尾指針

• 入隊：在鏈表尾端插入一個節(jié)點

• 出隊：刪除頭結點的后繼節(jié)點

4.隊列的面試題

• 劍指 Offer 面試題 7：用兩個棧實現(xiàn)一個隊列。隊列的聲明如下，請實現(xiàn)它的兩個函數(shù) appendTail() 和 deleteHead()，分別完成在隊列尾部插入結點和在隊列頭部刪除結點的功能。

private Stack<T> stack1;
private Stack<T> stack2; 

思路：我們從一個具體的例子來分析隊列的插入和刪除元素過程，操作兩三次，你就會發(fā)現(xiàn)刪除一個元素的步驟：當 stack2 中不為空的時候，在
stack2 中的棧頂元素就是最先進入隊列的元素，可以彈出。如果 stack2 為空時，我們把 stack1 的元素逐個彈出然后壓入 stack2 ，這樣就能保證
stack2 的棧元素順序就是進入隊列的順序。如果要使 stack1 的元素出棧，必須要彈完 stack2 的元素，然后將 stack1 的元素彈出壓入 stack2 ，再彈出 stack2 的元素。入隊的步驟就是將其壓入 stack1 中。

show my code

public class CQueue {

    public static void main(String[] args){  
        
        CQueue cQueue = new CQueue();

        cQueue.appendTail(111);
        cQueue.appendTail(222);
        cQueue.appendTail(333);
        System.out.println("出隊: " + cQueue.deleteHead());
        System.out.println("出隊: " + cQueue.deleteHead());
        
        cQueue.appendTail(444);
        cQueue.appendTail(555);
        System.out.println("出隊: " + cQueue.deleteHead());
        System.out.println("出隊: " + cQueue.deleteHead());
        System.out.println("出隊: " + cQueue.deleteHead());
        
        
    }
    
    //入隊的棧
    private Stack<Integer> stack1 = new Stack<>();
    // 出隊的棧
    private Stack<Integer> stack2 = new Stack<>();
    
    /**
     * 入隊
     * @param item
     */
    public void appendTail(Integer item){
        stack1.push(item);
    }
    
    /**
     * 出隊
     * @return
     */
    public Integer deleteHead(){
        
        //假如 stack2 為空棧，那么當前的隊列的頭結點肯定在 stack1 中，將 stack1 的元素全部彈出，然后入棧 stack2
        if(stack2.isEmpty()){
            while(stack1.size() > 0){
                Integer i = stack1.peek();
                stack1.pop();
                stack2.push(i);
            }
        }
        
        if(stack2.isEmpty()){
            System.out.println("隊列為空，刪除失敗");
            return -1;
        }
        
        Integer head = stack2.peek();
        stack2.pop();
        return head;
    }
}

驗證出隊順序

• 有個類似的題目：用兩個隊列實現(xiàn)棧。

思路：假設有兩個隊列Q1和Q2，當二者都為空時，入棧操作可以用入隊操作來模擬，可以隨便選一個空隊列，假設選Q1進行入棧操作，現(xiàn)在假設a,b,c依次入棧了（即依次進入隊列Q1）， 這時如果想模擬出棧操作，則需要將c出棧，因為在棧頂，這時候可以考慮用空隊列Q2，將a，b依次從Q1中出隊， 而后進入隊列Q2，將Q1的最后一個元素c出隊即可，此時Q1變?yōu)榱丝贞犃?，Q2中有兩個元素，隊頭元素為a，隊尾元素為b，接下來如果再執(zhí)行入棧操作，則需要將元素進入到Q1和Q2中的非空隊列，即進入Q2隊列，出棧的話，就跟前面的一樣，將Q2除最后一個元素外全部出隊，并依次進入隊列Q1，再將Q2的最后一個元素出隊即可。

show my code

public class QueueToStack<T> {
     
    //鏈隊
    Queue<T> queueA = new LinkedList<>();
    //鏈隊
    Queue<T> queueB = new LinkedList<>();
     
    /**
     * 入棧
     * @param value
     */
    public void push(T value) {
        if (queueA.size() == 0 && queueB.size() == 0) {//如果兩個隊列都是空的話,則隨便選擇一個隊列執(zhí)行入棧操作
            queueA.add(value);
        }else if (queueA.size() == 0 && queueB.size() != 0){///如果不是兩個隊列都是為空的話,則選擇非空的隊列入棧
            queueB.add(value);
        }else if (queueA.size() != 0 && queueB.size() == 0){
            queueA.add(value);
        }
    }
     
    /**
     * 出棧
     * @return
     */
    public T pop() {
        if (queueA.size() == 0 && queueB.size() == 0){
            return null;
        }
        
        T result = null;
        //將非空的隊列的元素按順序出隊，轉移到空的隊列，直到只有一個元素在非空隊列
        if (queueA.size() == 0 && queueB.size() != 0){
             while (queueB.size() > 0){
                 result = queueB.poll();
                 if (queueB.size()!=0){
                     queueA.add(result);
                 }
             }
         }else if (queueA.size() != 0 && queueB.size() == 0){
             while (queueA.size() > 0){
                 result = queueA.poll();
                 if (queueA.size()!=0){
                      queueB.add(result);
                 }
             }
         }
         return result;
    }
     
    public static void main(String[] args) {
        QueueToStack<Integer> stack=new QueueToStack<>();
        int tmp=0;
        stack.push(1);
        stack.push(2);
        stack.push(3);
        tmp=stack.pop();
        System.out.println(tmp);//3
        stack.push(4);
        tmp=stack.pop();
        System.out.println(tmp);//4
        tmp=stack.pop();
        System.out.println(tmp);//2
        stack.push(5);
        stack.push(6);
        tmp=stack.pop();
        System.out.println(tmp);//6
        tmp=stack.pop();
        System.out.println(tmp);//5
        tmp=stack.pop();
        System.out.println(tmp);//1
    }

}

出棧順序

三、詩和遠方

好了,最后兩分鐘,念幾句我在初學棧和隊列時寫的人生感悟的小詩,希望也能引起你們的共鳴。

人生,就像是一個很大的棧演變。 出生時你赤條條地來到人世,慢慢地長大,漸漸地變老,最終還得赤條條地離開世間。

人生,又仿佛是一天一天小小的棧重現(xiàn)。 童年父母每天抱你不斷地進出家門,壯年你每天奔波于家與事業(yè)之間,老年你每天獨自路跚于養(yǎng)老院的門里屋前。

人生,更需要有進棧出棧精神的體現(xiàn)。在哪里跌倒,就應該在哪里爬起來。無論陷入何等困境,只要抬頭就能仰望藍天,就有希望,不斷進取,你就可以讓出頭之日重現(xiàn)。困難不會永遠存在,強者才能勇往直前。

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

人生,又是一個又一個小小的隊列重現(xiàn)。 春夏秋冬輪回年年,早中晚夜循環(huán)天天。變化的是時間，不變的是你對未來執(zhí)著的信念。