c700. 壞掉的隊列(queue)
題目 Problem
題目連結:https://zerojudge.tw/ShowProblem?problemid=c700
敘述 Description
「測資中有若干行輸入,請你實作 queue 的幾種操作:
push $X(0≤X<2^{32})$: 將 $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。
輸入 Input
見題目和範例。
輸出 Output
輸出一行你要傳給小W的內容。
範例輸入 Sample Input
1 |
|
範例輸出 Sample Output
1 |
|
提示 Hint
輸入至多 100000 行。
以範例輸入而言,範例輸出一、二會拿到AC。
範例輸出三會拿到WA,因為操作4時堆疊二是空的。
範例輸出四也會拿到WA,因為輸入順序是push->push->pop->pop,但是1313的操作分別為push->pop->push->pop。
範例輸出五的操作過程完全合法,但依據先進先出的原則,111應該比222早離開queue,若以1133的方式操作,222將比111早輸出,所以會拿到WA。
題解 Solution
第一篇解題報告書就給這題啦!
Hackerrank 可以找到這個問題(這題就是要強制你使用 Stack)
實作 Queue 需要用到兩個 Stack
分別命名為$S1$跟$S2$
$S1$用來記錄輸入的東西
$S2$就是把$S1$的內容顛倒過來
$push$的時候先放入$S1$裡面
$pop$的時候先檢查$S2$有沒有東西
如果有,$S2$的頂端$pop$掉
如果沒有,先$S1$所有內容$pop$到$S2$,再讓$S2$的頂端$pop$掉
了解怎麼用 Stack 實作 Queue 就可以回到這題
依照上面的做法,可以使用代號$1,4,5$的組合或$2,3,6$的組合來完成這題
並且用$2$個整數紀錄$2$個 Stack 的內容數量
分別命名為$x_1$跟$x_2$
如果要$push$,就輸出$1$,把$x_1+1$
如果要$pop$,就先檢查$x_2$是否大於$0$
如果有,就輸出$4$,把$x_2-1$
如果沒有,先輸出$x_1$個$5$,讓$x_2$加上$x_1$,並且把$x_1$歸零,再輸出$4$,把$x_2-1$
這樣就可以來寫 Code 啦!
程式碼 Accepted Code
1 |
|
後記 Afterword
這題有沒有其他解法?
這題是 Special Judge,應該是有吧,但……我沒有想到
上面這個解法是算簡單啦
如果有更好的解法,我還會再寫上去啦!