e548 - 11995 - I Can Guess the Data Structure!
題目描述
題目給定一系列的插入和刪除操作，要求判斷這些操作所對應的資料結構是堆疊 (Stack)、佇列 (Queue) 還是優先權佇列 (Priority Queue)。如果無法確定，則輸出 "not sure"，如果以上三種都不符合，則輸出 "impossible"。
解題思路
這題的核心在於模擬三種資料結構的操作，並檢查給定的操作序列是否符合這些資料結構的特性。對於每一組輸入，我們分別使用堆疊、佇列和優先權佇列來模擬操作。如果在任何時刻，某種資料結構的操作與輸入不符，則將該資料結構的可能性標記為 false。最後，根據三種資料結構的可能性來判斷輸出結果。如果只有一種資料結構的可能性為 true，則輸出該資料結構的名稱。如果有多種可能性為 true，則輸出 "not sure"。如果三種可能性都為 false，則輸出 "impossible"。
複雜度分析
- 時間複雜度: O(n)，其中 n 是操作的數量。因為我們需要遍歷所有操作並模擬三種資料結構。
- 空間複雜度: O(n)，因為在最壞的情況下，三種資料結構都需要儲存所有輸入的元素。
程式碼
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,is,v;
while(cin >> n){
bool s=1,q=1,p=1;
stack <int> ss;
queue <int> qq;
priority_queue <int> pp;
for(int i=0;i<n;++i){
cin >> is >> v;
if(is==1){
if(s)
ss.push(v);
if(q)
qq.push(v);
if(p)
pp.push(v);
}
else{
if(s){
if(ss.empty()||ss.top()!=v)
s=0;
else
ss.pop();
}
if(q){
if(qq.empty()||qq.front()!=v)
q=0;
else
qq.pop();
}
if(p){
if(pp.empty()||pp.top()!=v)
p=0;
else
pp.pop();
}
}
}
if(s+q+p>1)
cout << "not sure\n";
else if(s+q+p==0)
cout << "impossible\n";
else if(s)
cout << "stack\n";
else if(q)
cout << "queue\n";
else if(p)
cout << "priority queue\n";
}
}