stackとqueueの紹介

データ構造って何

データ構造は コンピューター上でデータを効率よく保存、管理するための方法です.

おいしいデータ構造を使うことで, 例えばデータの検索や追加、削除などの操作を高速に行うことができます.

しかも自分で処理を書くよりも, すでに用意されているデータ構造||用意したデータ構造を用いることで, コードの可読性が上がり, バグを減らすことができます.

参考：https://zenn.dev/brainyblog/articles/data-structures-beginners-guide

今日扱うもの

計算量の話

データ構造を選ぶ基準は「その操作が何回のステップで終わるか」です. これを 計算量 と呼び, O(1), O(N), O(log N) のように書きます.

• O(1) : データが何個あっても一定時間. 速い.
• O(log N) : データが100万個でも20回程度. かなり速い.
• O(N) : データの個数に比例. 100万個なら100万回. AtCoderでは 1秒間に 10^8 回 程度の計算ができると考えてください. N = 10^5 のデータに対して O(N) の操作を N 回繰り返すと O(N^2) = 10^10 回になり, 間に合いません.

これが「適切なデータ構造を選ぶ」ということの意味です.

(最悪)計算量算出

高校数学で, 極限をを習った人もいると思います. 計算量の算出方法としては, nを大きくしたときに一番影響をが出てくる項を係数なしで残すのが基本です. 例えば, 以下のような式があったとします.

f(n) = 3n^2 + 5n + 7

この場合はnが大きくなると3n^2が最も大きくなるので, n^2の項を残します. さらには, nが大きくなると係数があまり影響しなくなるので省きます. したがって, f(n)の計算量はO(n^2)となります.

このたとえが分かりにくい人がいるかもしれません. 具体例として, n=1億みたいな大きい数字を入れてみると,

f(10^8) = 3*10^16 + 5*10^8 + 7

となります. 3*10^16が圧倒的に大きいので, 5*10^8や7は無視してもあんまり変わらなそう…という感じの捉え方です. さらには係数も無視も. 10^16の3倍と1倍では, 10^16の中ではあまり変わらないので, 係数も無視してよさそう…という感じです.

競プロではこういう見積もりを良くします.

queue

FIFO（先入れ先出し）

先に入れたものが先に出てくる データ構造です. 行列（レジ待ち）をイメージしてください.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    queue<int> q;
 
    q.push(1);   // 末尾に追加
    q.push(2);
    q.push(3);
 
    cout << q.front() << endl;  // 1 (先頭を見る)
    q.pop();                    // 先頭を削除（値は返らない！）
    cout << q.front() << endl;  // 2
 
    cout << q.size() << endl;   // 2
    cout << q.empty() << endl;  // 0 (空ならtrue)
}

Javaとの違い

ここが最大の落とし穴です.

Javaの Queue は poll() が 値を返しながら削除 します.

int x = q.poll();  // 取り出して削除

C++の queue は front() で見る と pop() で削除する が分離しています.

int x = q.front();  // 見るだけ
q.pop();            // 削除するだけ（戻り値なし）

int x = q.pop(); と書くとコンパイルエラーになります. 必ず2行に分けてください.

空のqueueに対する操作

q.empty() が true のときに q.front() を呼ぶと 未定義動作 です. エラーにならず, 変な値が返ってきたり, 実行時エラーになったりします.

Javaの poll() は空なら null を返してくれますが, C++は何も守ってくれません. ループの条件に !q.empty() を必ず入れる癖をつけてください.

while (!q.empty()) {
    int x = q.front();
    q.pop();
    // xを使う処理
}

使いどころ

queue の主戦場は 幅優先探索（BFS） です. 迷路の最短経路を求めるときなどに使います.

BFSは今日は扱いませんが, 「近いところから順番に調べる」という処理は queue が担当する, と覚えておいてください.

例題

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_az https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_dy

stack

LIFO（後入れ先出し）

後に入れたものが先に出てくる データ構造です. 積み上げた本の山をイメージしてください. 上から取るしかありません.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    stack<int> st;
 
    st.push(1);  // 積む
    st.push(2);
    st.push(3);
 
    cout << st.top() << endl;  // 3 (一番上を見る)
    st.pop();                  // 一番上を削除
    cout << st.top() << endl;  // 2
 
    cout << st.size() << endl;  // 2
    cout << st.empty() << endl; // 0
}

queueとの対応

見るときのメソッド名だけが違います. stack は「上を見る」ので top() です.

pop() が値を返さないのは queue と同じです.

使いどころ

括弧の対応チェック, 逆ポーランド記法の計算, 深さ優先探索（DFS）の非再帰実装などです.

「直前の状態に戻る」「入れ子構造を処理する」というパターンが出てきたら stack を疑ってください.

括弧の対応チェック

典型例なので, コードを見ておきましょう.

bool is_valid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') {
            st.push(c);
        } else {  // c == ')'
            if (st.empty()) return false;  // 閉じすぎ
            st.pop();
        }
    }
    return st.empty();  // 開きっぱなしがなければOK
}

( が来たら積み, ) が来たら取り除く. 最後に空ならバランスが取れている, という考え方です.

例題

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ay https://atcoder.jp/contests/joi2022yo2/tasks/joi2022_yo2_a https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_dx