劍指 Offer 09. 用兩個棧實作隊列（視訊講解）

一、題目描述

用兩個棧實作一個隊列。隊列的聲明如下，請實作它的兩個函數 ​

​appendTail​

​​ 和 ​

​deleteHead​

​​ ，分别完成在隊列尾部插入整數和在隊列頭部删除整數的功能。(若隊列中沒有元素，​

​deleteHead​

​​ 操作傳回 ​

​-1​

​ )

示例 1：

輸入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
輸出：[null,null,3,-1]      

示例 2：

輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]      

• ​

  ​1 <= values <= 10000​

  ​
• ​

  ​最多會對 appendTail、deleteHead 進行 10000 次調用​

  ​

二、保姆級參考代碼

// 登入 AlgoMooc 官網擷取更多算法圖解
// https://www.algomooc.com
// 作者：程式員吳師兄
// Java 中的 Stack 類設計有問題，大部分情況下是使用 LinkedList 來建構棧，但為了結合動畫更好的了解這道題目，是以依舊使用 Stack 
class CQueue {

    // 隊列的特點，先進先出
    // 棧的特點是先進後出
    // 建立兩個棧
    // 建立棧 stack1 用來充當隊列
    Stack<Integer> stack1;
    
    // 建立棧 stack2 用來輔助 stack1 執行隊列的一些複雜操作
    Stack<Integer> stack2;
    
    // 這個函數是 creat queue
    // 意思就是初始化隊列
    // 由于題目要求我們用兩個棧實作隊列，是以在這個函數中初始化的是兩個棧
    public CQueue() {

        // 初始化 stack1 
        stack1 = new Stack<Integer>();

        // 初始化 stack2 
        stack2 = new Stack<Integer>();

    }
    
    // 這個函數的意思是在隊列的尾部添加元素
    // 使用棧來完成這個操作的話就是在 stack1 的後面添加元素就行
    public void appendTail(int value) {

        // 直接将元素存放到 stack1 中
        // 比如原隊列為
        //       -------------
        //  隊尾  1  2  3  4  5  隊頭
        //       -------------
        // 目前 value 為 6 
        // 那麼由 stack1 和 stack2 組成的隊列就是
        //       ----------------
        //  隊尾  6  1  2  3  4  5  隊頭
        //       ----------------
        stack1.push(value);

    }
    
    // 這個函數的意思是在隊列的頭部删除元素
    // 由于隊列的特點是先進先出，是以需要借助 stack1 和 stack2 去定位到之前存儲進來的元素
    public int deleteHead() {

        // 1、如果 stack2 棧不為空，說明 stack2 裡面已經存儲了一些元素，
        // 并且 stack2 的棧頂元素就是兩個棧中最早加入的元素
        if(!stack2.isEmpty()){
            // 傳回 stack2 的棧頂元素，滿足了隊列先進先出的特點
            return stack2.pop();
        }

        // 2、如果 stack2 為空，并且發現 stack1 也為空，
        // 說明 stack1 和 stack2 建構的隊列中沒有元素，
        if(stack1.isEmpty()){
            // 根據題意，直接傳回 -1
            return -1;
        }

        // 3、如果 stack2 為空，但 stack1 不為空
        // 那麼需要先将 stack1 中的元素依次【倒序】放入 stack2 中
        // 對于 stack1 來說，越早加入的元素在【棧底】，越晚加入的元素在【棧頂】
        // 由于隊列是【先進先出】，是以删除的應該是 stack1 的【棧底】元素
        while(!stack1.isEmpty()){
            // 擷取 stack1 的棧頂元素并将該元素從 stack1 中彈出
            int topValue = stack1.pop();
            // 把該元素加入到 stack2
            // 這樣 stack2 的棧頂元素就是 stack1 的棧底元素
            stack2.push(topValue);
        }

        // 4、傳回 stack2 的棧頂元素，滿足了隊列先進先出的特點
        return stack2.pop();
    }
}      

三、視訊講解