c700: 壞掉的隊列 (queue)

2019-08-25

內容

「測資中有若干行輸入，請你實作 queue 的幾種操作：

push X(0≤X<2³²): 將 X 加入隊列

pop: 輸出隊列最前方的數字並刪除，你可以假設此時隊列不是空的」

小 W 本來想隨便寫寫交差了事，卻發現 STL 的 queue 壞了！

再看看題目，原來底下附註一行小字：請用兩個 stack 完成這題。

於是小 W 希望你能用以下代號寫一張紙條告訴他該怎麼做。

1: 讀入 push X 並將 X 放到堆疊一

2: 讀入 push X 並將 X 放到堆疊二

3: 讀入 pop ，將堆疊一頂端的元素輸出並刪除

4: 讀入 pop ，將堆疊二頂端的元素輸出並刪除

5: 將堆疊一頂端的元素取出並放至堆疊二

6: 將堆疊二頂端的元素取出並放至堆疊一

如果取出元素時堆疊為空或者讀入 push/pop 的順序與輸入測資不符，你會害小 W 拿到一個 WA。

輸入

見題目和範例。

push 111
push 222
pop
pop

輸出

輸出一行你要傳給小 W 的內容。

範例輸出一：
1234

範例輸出二：
12544

範例輸出三：
1143

範例輸出四：
1313

範例輸出五：
1133

提示

輸入至多 100000 行。

以範例輸入而言，範例輸出一、二會拿到 AC。

範例輸出三會拿到 WA，因為操作 4 時堆疊二是空的。

範例輸出四也會拿到 WA，因為輸入順序是 push->push->pop->pop，但是 1313 的操作分別為 push->pop->push->pop。

範例輸出五的操作過程完全合法，但依據先進先出的原則，111 應該比 222 早離開 queue，若以 1133 的方式操作，222 將比 111 早輸出，所以會拿到 WA。

解題思路

用兩個 stack 模擬 queue，重點觀念是 stack 的輸出順序是反向的，但如果先把 stack 存到另一個 stack 再輸出，根據負負的正定理，新 stack 的輸出順序就會變成正常的，如以下範例

輸入 = 1 2 3 4 5
依序 push 進 stack1
stack1 = 1 2 3 4 5
再將 stack1 依序 pop 出並 push 進 stack2
stack2 = 5 4 3 2 1
最後將 stack2 依序 pop 輸出
輸出 = 1 2 3 4 5

也就是說實作時

指令為 push 時，將輸入的東西都存進 stack1，
指令為 pop 時，看 stack2 還有沒有剩餘的元素，有就 pop 出該元素，否則將 stack1 依序 pop 到 stack2
由於本題並不需要輸出任何有關輸入的的元素，所以可以無視它用兩個 int 模擬 stack 的長度來做就行了。

完整程式碼

AC (46ms, 704KB)

#include <stdio.h>

int s1Len, s2Len;
char cmd[20], output[200000], * oTop = output;

int main()
{
    while (gets(cmd) != NULL)
    {
        if (cmd[1] == 'u')
        {
            s1Len++;
            *oTop++ = '1';
        }
        else if (s2Len)
        {
            *oTop++ = '4';
            s2Len--;
        }
        else
        {
            s2Len = s1Len - 1;
            while (--s1Len)
                * oTop++ = '5';
            *oTop++ = '5', * oTop++ = '4';
        }
    }
    puts(output);
    return 0;
}