- 物理機リージョン/AZ
- ハイパーバイザVM exit で捕まえる
- VMゲストOS
- コンテナnamespace / cgroup
- プロセスアプリ / DB今ここ
メモリ上に並べたデータを、どの順で取り出すか。逐語と実測はいずれも2026年9月17日のものです。
まず結論
キューとスタックは「入れ物」が違うのではなく、**取り出す規則**が違うだけです。cppreference は両方を container adaptor と説明し、Python の `queue` 公式は3種類の差を "which differ only in the order in which the entries are retrieved" と書いています。
そして取り出し規則は、探索の形そのものを決めます。同じグラフ・同じ挿入順で、先頭から取れば2ホップ、末尾から取れば4ホップの経路が見つかりました(Python 3.13.15 での実測・後述)。
同じグラフに対し、同じ順序で行き先を積み、探索の手順も全く同じにします。違うのは「積んだものを先頭から取るか、末尾から取るか」だけです。見つかる経路はどうなるでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
違うのは入れ物ではなく、取り出す端
キューとスタックは「別のデータ構造」として並べて教えられます。しかし一次ソースでは、両者の差はもっと狭いところにあります。cppreference の std::queue です。
The std::queue class template is a container adaptor that gives the functionality of a queue - specifically, a FIFO (first-in, first-out) data structure.
std::stack はこうです。
The std::stack class is a container adaptor that gives the programmer the functionality of a stack - specifically, a LIFO (last-in, first-out) data structure.
どちらも container adaptor です。そして両ページに、同じ一文が置かれています。
The class template acts as a wrapper to the underlying container - only a specific set of functions is provided.
新しい入れ物ではなく、既存の入れ物を包んで使える操作を絞ったものだと書いてあります。既定の下層コンテナはどちらも std::deque で同一です。
The queue pushes the elements on the back of the underlying container and pops them from the front.
The stack pushes and pops the element from the back of the underlying container, known as the top of the stack.
同じ std::deque に、片方は前から取る規則、もう片方は後ろから取る規則を被せた差です。
別の言語の公式文書が、同じことを言っている
Python の queue モジュールの冒頭にも、同じ構造が現れます。
The module implements three types of queue, which differ only in the order in which the entries are retrieved. In a FIFO queue, the first tasks added are the first retrieved. In a LIFO queue, the most recently added entry is the first retrieved (operating like a stack). With a priority queue, the entries are kept sorted (using the heapq module) and the lowest valued entry is retrieved first.
"which differ only in the order in which the entries are retrieved" — 3つのクラスの差は取り出される順序だけだと公式が明言しています。C++ の container adaptor という説明と同じ構造です。
言語もライブラリも違うのに、どちらの一次ソースも「格納が違う」とは書いていません。書いてあるのは「取り出し方が違う」です。
「キューとスタックは、データの格納のしかたが違うデータ構造である」という説明を cppreference の記述に照らすとどう評価できますか。
取り出し規則は、速さではなく探索の形を決める
取り出し規則の違いは、単に順番が入れ替わるという話ではありません。次にどこを見るかを決めるので、探索が進む方向そのものが変わります。
探索では、行き先の候補を溜める置き場(フロンティア)を持ちます。ある地点に着いたら隣を全部入れ、そこから1つ取り出して次へ進む。この手順はキューでもスタックでも同じです。
- 先頭から取れば、先に入れた候補が先に処理される。入れた順は近い順なので近くから広がる — 幅優先
- 末尾から取れば、最後に入れた候補が先。それは今いる地点の隣なので、そのまま奥へ降りる — 深さ優先
- ・分かれるのは2段目だけ。データも入れ方も同じ
- ・優先度で取り出す規則を被せると、また別の探索になる
第3の規則もあります。優先度で取り出すもので、重み付きの経路探索(ダイクストラ法)の土台です。FIFO・LIFO・優先度は置き場の使い方の3通りであって、別々の世界の話ではありません。
実測 — 変えたのは1文字、結果は2ホップと4ホップ
Docker の python:3.13-slim(Python 3.13.15、--network=none、1回実行。決定的なため反復していません)での生出力です。
graph: {'S': ['X', 'A'], 'X': ['G'], 'A': ['B'], 'B': ['C'], 'C': ['G'], 'G': []}both searches push neighbours in the same order: X before AFIFO (queue: remove from front) == breadth-firstvisit order: S X A Gpath found : S -> X -> G hops: 2LIFO (stack: remove from back) == depth-firstvisit order: S A B C Gpath found : S -> A -> B -> C -> G hops: 4Same graph, same insertion order. Only the REMOVAL rule differs,and the two searches reach the goal by different routes.
グラフも、近傍を積む順序(X が先、A が後)も同じ。違うのは frontier.pop(0) か frontier.pop() かだけです。それで訪問順が S X A G と S A B C G に割れ、経路が 2 ホップと 4 ホップに分かれました。
「名前に queue と付いていれば先入れ先出しである」という前提はどう評価できますか。
先頭から取る(FIFO)— 近いものから見つかる
置き場に先に入った候補から処理します。先に入るのは出発点に近い候補なので、探索は層状に外へ広がります。実測では訪問順が `S X A G` となり、`S -> X -> G`(2ホップ)に到達しました。
末尾から取る(LIFO)— 1本道を最後まで辿る
置き場に最後に入った候補から処理します。最後に入ったのは今いる地点の隣なので、探索は引き返さずに奥へ降り続けます。実測では訪問順が `S A B C G` となり、4ホップで到達しました。
2つの探索は同じグラフを、同じ順序で積みながら走っています。それでも結果が割れました。両者を分けている唯一の差は何で、それはなぜ結果を変えるのでしょうか。
コードの差は1文字です。`pop(0)` か `pop()` か。その1文字が毎周ごとに「次にどこを見るか」を選び直しています。
優先度で取り出すとき、費用はどう書かれているか
優先度付きキューは「優先度の順に取り出せる置き場」です。cppreference の概要文を見ます。
The priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
参照と取り出しが分けて書かれている点が重要です。先頭を見る(top())のは constant time、挿入と取り除きが logarithmic。「取り出しが O(log n)」とまとめると、top() と pop() のどちらの話か分からなくなります。
push の Complexity 欄はこうです。
Logarithmic number of comparisons plus the complexity of Container::push_back.
cppreference は 「O(log n)」とは書いていません。対数なのは比較の回数で、それに下層コンテナの push_back の費用が足されます。pop 側も Logarithmic number of comparisons plus the complexity of Container::pop_back. です。plus 以下を落とすと、どのコンテナを下に敷くかが費用に効くという事実が消えます。
取り出す順序が保証されていても、中身は並んでいない
Python の queue 公式は、優先度付きキューについて the entries are kept sorted (using the heapq module) と書いています。では中身は整列しているのか。heapq を直接動かした生出力です。
--- heapq: insertion order vs pop order ---after heappush (3, 'low') -> heap[0] = (3, 'low') list = [(3, 'low')]after heappush (1, 'urgent') -> heap[0] = (1, 'urgent') list = [(1, 'urgent'), (3, 'low')]after heappush (2, 'mid') -> heap[0] = (1, 'urgent') list = [(1, 'urgent'), (3, 'low'), (2, 'mid')]heappop order: [(1, 'urgent'), (2, 'mid'), (3, 'low')]
最後の push のあと、リストは [(1, 'urgent'), (3, 'low'), (2, 'mid')] で整列していません。それでも heappop は 1 → 2 → 3 の順で返します。保たれているのは、heapq 公式が heap invariant と呼ぶ条件だけです。
Min-heaps are binary trees for which every parent node has a value less than or equal to any of its children. We refer to this condition as the heap invariant.
親が子以下、という条件です。公式はこう続けます。
The interesting property of a min-heap is that its smallest element is always the root, heap[0].
最小が先頭にいることは保証されるが、残りの並びは保証されない。 kept sorted という語を「リスト全体が整列している」と読むと、この実測と食い違います。正確に言えるのは、リスト全体が並んでいるわけではなく、取り出す順序が保証されているということです。
ブラウザ編『イベントループ — タスクは集合、マイクロタスクは待ち行列』でも、HTML 仕様が task queue を set と定義していることを見ました。名前や散文の言い回しではなく、取り出し規則の定義を読みに行く — その型がここでも要ります。
この章のまとめ
- cppreference は
std::queueもstd::stackも container adaptor と説明し、"only a specific set of functions is provided" と書く。既定の下層コンテナはどちらもstd::deque。 - Python の
queue公式も3種類の差を "which differ only in the order in which the entries are retrieved" と述べる。差は格納ではなく取り出し順。 - 取り出し規則は探索の形を決める。実測(Python 3.13.15)では同じグラフ・同じ挿入順で 先頭から取ると2ホップ、末尾から取ると4ホップに割れた。変えたのは
pop(0)かpop()かだけ。 - ただしこの1例は「幅優先が常に最短を返す」の証明ではない。それは辺の重みが等しい場合の性質。
- 優先度付きキューの費用は cppreference では "Logarithmic number of comparisons plus the complexity of Container::push_back."。
top()は constant、pop()が logarithmic と分けて書かれている。 heapqの内部リストは整列していない(実測[(1,'urgent'), (3,'low'), (2,'mid')])。保たれるのは heap invariant だけ。リスト全体が並んでいるのではなく、取り出す順序が保証されている。- 名前が queue でも FIFO とは限らない。確かめる先は名前ではなく取り出し規則の定義。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
同じグラフ・同じ挿入順で幅優先と深さ優先の結果が割れるのは、何が違うからですか。
用語集(5語)
- FIFO(先入れ先出し)
- 先に入れたものから取り出す規則。cppreference は `std::queue` を "a FIFO (first-in, first-out) data structure" と説明する。探索に使うと幅優先になる。
- LIFO(後入れ先出し)
- 後に入れたものから取り出す規則。cppreference は `std::stack` を "a LIFO (last-in, first-out) data structure" と説明する。探索に使うと深さ優先になる。
- container adaptor
- cppreference が `std::queue` と `std::stack` に使う語。既存のコンテナを包んで "only a specific set of functions is provided" とする仕組み。既定の下層はどちらも `std::deque`。
- 優先度付きキュー
- 入れた順ではなく優先度で取り出すもの。cppreference の `std::priority_queue` は "constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction" と記述される。
- heap invariant(ヒープ不変条件)
- heapq 公式の語。"Min-heaps are binary trees for which every parent node has a value less than or equal to any of its children." 親が子以下であることだけを保つので、全体は整列しない。