UVA-11995 - I Can Guess the Data Structure!

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20160524 大學程式能力檢定 CPE」題目。

題意概要

題目有個像袋子一樣的資料結構，並提供兩種操作：

現在給你一連串的序列，包含上述的兩種操作與回傳值，請猜出袋子是何種資料結構。有可能是堆疊 (Stack) [後進先出] 或 佇列 (Queue) [先進先出] 或優先權佇列 (Priority Queue) [每次拿出較大的元素]，也有可能是其他你沒有想到的東西。

• 分析：本題為資料結構的觀念題，在 C++ STL 中已提供題目的每一種資料結構，因此直接模擬每一種資料結構的狀況即可，唯獨要注意的是，再取值或使用 pop() 的時候要記得先判斷「容器是否為空」，否則會出現執行錯誤。

Input

There are several test cases. Each test case begins with a line containing a single integer $n$ ($1 \le n \le 1,000$). Each of the next $n$ lines is either a type-1 command, or an integer 2 followed by an integer $x$. That means after executing a type-2 command, we get an element $x$ without error. The value of $x$ is always a positive integer not larger than 100. The input is terminated by end-of-file (EOF).

Output

For each test case, output one of the following:

Sample Input

6
1 1
1 2
1 3
2 1
2 2
2 3
6
1 1
1 2
1 3
2 3
2 2
2 1
2
1 1
2 2
4
1 2
1 1
2 1
2 2
7
1 2
1 5
1 1
1 3
2 5
1 4
2 4

Sample Output

queue
not sure
impossible
stack
priority queue