JOI 二次予選 2022 A - 図書館 2 (AOJ 0719) (4Q, 難易度 2)

スタックを用いたシミュレーション問題！

• 問題へのリンク

問題概要

最初、本は積まれていない。次の 回のクエリに答えよ

【クエリ】
各クエリでは文字列 が与えられる。

• が "READ" ではないとき、タイトルが である本が新たに上に積まれる
• が "READ" であるとき、積まれた本の一番上にある本を取り除いて、その本のタイトルを出力する

制約

• 
• クエリ "READ" が呼ばれるとき、少なくとも 1 冊以上の本が積まれていることが保証される

解法

これはスタックと呼ばれるデータ構造の挙動を実装せよ、という問題です。スタックについては、次の記事を参照してください。

qiita.com

スタックは、この問題のように「要素を取り出すとき、最も直近で挿入された要素を取り出す」という挙動を実現するデータ構造のことです。この挙動は、LIFO (Last-In First-Out) とも呼ばれます。

実装するためには、たとえば vector<string> 型が使えます。この型の変数を stk などとするとき、

---

• 末尾に要素 v を挿入する操作は、stk.push_back(v)
• 末尾の要素 (最も直近で挿入された要素) は、stk.back() でアクセス可能
• 末尾の要素を削除する操作は、stk.pop_back()

---

と実装できます。このことを利用して、スタックを実装できます。いずれも平均的に の計算量で実現します。

よって、この問題は の計算量で解けます。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<string> stk;
    for (int i = 0; i < N; i++) {
        string S;
        cin >> S;
        if (S == "READ") {
            cout << stk.back() << endl;
            stk.pop_back();
        } else {
            stk.push_back(S);
        }
    }
}