用兩個棧實作隊列（C++簡單區）

用兩個棧實作隊列

題目：用兩個棧實作一個隊列。隊列的聲明如下，請實作它的兩個函數 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 次調用

題目解讀

剛開始看到題目後有點懵，一時不知道例子是什麼意思，在看完别人的解析後才明白例子的含義。

[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”] ：這裡表示的是按順序執行每一步函數操作。然後[[],[3],[],[]]代表每一個函數所需要的參數。

舉例：

CQueue 表示建立一個CQueue對象，對應的所需參數為[]，即此操作不需要參數。

appendTail 表示執行一個appendTail()操作，函數對應要所需要的參數為3。

deleteHead 表示執行一個deleteHead操作，對應的所需參數為[]，即此操作不需要參數。

deleteHead 表示執行一個deleteHead操作，對應的所需參數為[]，即此操作不需要參數。

解題思路

我們知道棧滿足的是先進後出（FILO）規則，而隊列滿足的則是先進先出（FIFO）規則。是以要想實作用兩個棧實作隊列就要讓一個棧完成添加元素的操作，另一個棧實作删除元素的操作。

這裡我們定義棧s1完成壓入元素操作，棧s2完成去除元素操作。

首先完成兩個棧的初始化操作，使其初始化為兩個空棧。當有資料壓入s1時，我們直接将元素壓入棧s1，但是由于先進的元素會壓入棧底，是以為了實作隊列先進先出的特點，我們在要删除元素時将s1中的元素全部壓入到s2中，這樣就實作了類似于将s1中元素反轉壓入s2，就能很好的滿足隊列的特點。不過在将s1元素壓入s2中要確定s2此時是空棧，因為如果s2中有元素時，在我們要再次向s2中壓入元素時，會将先前壓入的元素又處于s2的棧底，這樣就又不滿足隊列的特點了。

在s2為空棧的前提下，我們将s1中元素全部壓入s2，完成這部操作後如果此時s2仍然為空棧，則說明s1、s2中都沒有元素存在，此時則傳回-1。

若s2不為空棧時，我們擷取s2棧頂元素後将其棧頂元素删除，最後傳回先前保留住的棧頂元素。

下面用動圖來描述一下整個壓入和删除的過程：

代碼展示

代碼如下：

class CQueue {
public:
/*s1棧用作添加元素
 *s2棧用作删除元素
 */
    stack<int>s1,s2;
    CQueue() {
        //初始化s1
        while(!s1.empty())
        {
            s1.pop();
        }
        //初始化s2
        while(!s2.empty())
        {
            s2.pop();
        }
    }
    //将添加的元素直接壓入s1
    void appendTail(int value) {
        s1.push(value);
        return;
    }
    
    int deleteHead() {
        //如果s2棧為空時直接将s1中元素全部壓入s2
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        //如果此時棧s2還是為空，則說明兩個棧中都沒有元素，傳回-1
        if(s2.empty())
        {
            return -1;
        }
        //如果s2不為空，則将棧頂元素取出并傳回棧頂元素
        else
        {
            int elem=s2.top();
            s2.pop();
            return elem;
        }
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */
 執行用時：644 ms, 在所有 C++ 送出中擊敗了90.54%的使用者
 記憶體消耗：103.6 MB, 在所有 C++ 送出中擊敗了78.96%的使用者