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

push 111
push 222
pop
pop

範例輸出 Sample Output

範例輸出一:
1234

範例輸出二:
12544

範例輸出三:
1143

範例輸出四:
1313

範例輸出五:
1133

提示 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

#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
	_
	string enter;
	int total1=0,total2=0;
	while(cin>>enter){
		if(enter=="push"){
			long long int a;
			cin>>a;
			total1++;
			cout<<1;
		}
		else{
			if(total2){
				cout<<4;
				total2--;
			}
			else{
				for(int i=0;i<total1;i++){
					cout<<5;
				}
				total2+=total1;
				if(total2){
					cout<<4;
					total2--;
				}
				total1=0;
			}
		}
	}
	return 0;
}

後記 Afterword

這題有沒有其他解法？
這題是 Special Judge，應該是有吧，但……我沒有想到
上面這個解法是算簡單啦
如果有更好的解法，我還會再寫上去啦！