UVa #11995 I Can Guess the Data Structure!

問題の概要


問題文: UVa Online Judge #11995 - I Can Guess the Data Structure!

  n個の命令文が入力として与えられる。 以下のデータ構造のうち、どのデータ構造に大した命令文であったか出力するもの。

  • Stack
  • Queue
  • Priority queue

 また、一つに限定できない場合はnot sure、どのデータ構造でもない場合はimpossibleを出力する。

解答例


 単にC++にあるstack、queue、priority queueにコマンドと同じ操作をさせて同じ挙動を取るかどうかで判断するだけで良い。 しかし、データが挿入されていない状態で、データを参照・削除をする場合の処理を忘れないように気をつける。

 以上のソースコードは以下のGithub上にて参照可能です。 github.com

データ構造について


スタック(Stack)

概要

 スタックが可能な操作は以下の通りである。

  • Push: 新たなデータを追加する操作
  • Pop: 最も最近に追加されたデータを取り出す操作

C++ におけるstd::stackの使い方

 C++ では、Pushはpush()にて、Popはtop() / pop()にて実現できる。

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> st;
    
    for(int i = 0; i < 10; i++){
        st.push(i);  //スタック st に i を追加する
    }
    
    while(!st.empty()){
        cout << st.top() << " ";  // stの末尾要素を参照(出力)
        st.pop();  // stの末尾要素を削除
    }
}

 入力が0, 1, 2, 3, 4, 5, 6, 7, 8, 9の順に対して、出力は9 8 7 6 5 4 3 2 1 0となる。

キュー(Queue)

概要

 キューが可能な操作は以下の通りである。

  • Enqueue: 新たなデータを追加する操作
  • Dequeue: 最初に追加されたデータを取り出す操作

C++ におけるstd::queueの使い方

 C++ では、Enqueueはpush()にて、Dequeueはfront() / pop()にて実現できる。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    
    for(int i = 0; i < 10; i++){
        q.push(i); //キュー q に i を追加する
    }
    
    while(!q.empty()){
        cout << q.front() << " ";  // qの先頭要素を参照(出力)
        q.pop(); // qの先頭要素を削除
    }
}

 入力が0, 1, 2, 3, 4, 5, 6, 7, 8, 9の順に対して、出力は0 1 2 3 4 5 6 7 8 9となる。

優先度付きキュー(Priority queue; 順位キュー)

概要

 優先度付きキューが可能な操作は以下の通りである。

  • 新たなデータを追加する操作
  • 優先度が高いデータ(昇順 / 降順)を取り出す操作

C++ におけるstd::priority_queueの使い方

 C++ では、データの挿入はpush()にて、データの参照 / 削除はtop() / pop()にて実現できる。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;
    int inputs[10] = {0, 5, 4, 9, 2, 1, 3, 7, 8, 6};
    
    for(int i = 0; i < 10; i++){
        pq.push(inputs[i]);
    }
    
    while(!pq.empty()){
        cout << pq.top() << " "; // pqの優先度の一番高い要素を参照(出力)
        pq.pop(); // pqの優先度の一番高い要素を削除
    }
}

 入力が0, 5, 4, 9, 2, 1, 3, 7, 8, 6の順に対して、出力は9 8 7 6 5 4 3 2 1 0となる。