# 題目: UVa 11995 - I Can Guess the Data Structure!
# 題目說明
你能猜到資料結構嗎?
給你一些 push
和 pop
data,找出資料結構
INPUT:
每筆資料的第一行有一個整數 n
,代表接下來有 n
行
每行有兩個整數,前者代表指令, 1
為 push
, 2
為 pop
,後者代表數字
OUTPUT:
stack
queue
priority queue
- 都不是
impossible
- 兩種以上容器符合
not sure
# 解題方法
分別 push
到 3 種容器中做模擬,看有幾個符合
# 參考程式碼
#include <iostream> | |
#include <queue> | |
#include <stack> | |
using namespace std; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int n, in, x; | |
while (cin >> n) { | |
queue<int> q; | |
priority_queue<int> pq; | |
stack<int> s; | |
bool isq = true, ispq = true, iss = true; | |
while (n--) { | |
cin >> in >> x; | |
if (in == 1) { | |
q.emplace(x); | |
pq.emplace(x); | |
s.emplace(x); | |
} | |
else { | |
if (isq) | |
if (!q.empty() && q.front() == x) q.pop(); | |
else isq = false; | |
if (ispq) | |
if (!pq.empty() && pq.top() == x) pq.pop(); | |
else ispq = false; | |
if (iss) | |
if (!s.empty() && s.top() == x) s.pop(); | |
else iss = false; | |
} | |
} | |
if ((isq && iss) || (isq && ispq) || (ispq && iss)) cout << "not sure\n"; | |
else if (isq) cout << "queue\n"; | |
else if (ispq) cout << "priority queue\n"; | |
else if (iss) cout << "stack\n"; | |
else cout << "impossible\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://www.larrysprognotes.com/UVa%20-%2011995/