ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

スタックとキュー

回 2-4　道 2 データ構造とアルゴリズム

スタックとキューは、データを 1 列にしまう形で、スタックは後から入れた物が先に出る (LIFO、後入れ先出し) しまい方、キューは先に入れた物が先に出る (FIFO、先入れ先出し) しまい方です。元に戻す機能は、操作の前の状態をスタックに積み、新しい物から 1 つずつ取り出すので作れます。Python では、スタックは list の append と pop、キューは collections.deque の append と popleft で書けます。

目安 45 分2-4 (2-0〜2-10 の中)

読み終えたら元に戻す機能がスタックで作れる理由を説明できる

この頁の流れ

  1. 1「元に戻す」は、なぜ新しい操作から戻るのか
  2. 2スタックとキューはどう違うのか
  3. 3動かして確かめる
  4. 4スタックとキューはどこで崩れるのか
  5. 5スタックとキューは仕事でどう確かめるのか
  6. 6関わる実例
  7. 7よくある問い
  8. 8確認クイズ
  9. 9説明課題
  10. 10もっと深く
  11. 11一次資料
  12. 12次へ

出し入れの順が「新しい物から」か「古い物から」かで、スタックとキューを使い分けられるようになります。

文 ゆめさくコード編集部公開 2026年10月26日更新 2026年10月26日出典を確かめた日 2026年10月26日

「元に戻す」は、なぜ新しい操作から戻るのか

元に戻す機能は、操作の前の状態を順に積み重ね、一番上 (一番新しい物) から取り出すしまい方で作られています。このしまい方をスタックと呼びます。

文書を書いていて、3 回打ち込んだあとに「元に戻す」を押すと、消えるのは最後に打った分です。もう一度押すと、その前の分が消えます。古い操作から戻ることはありません。

一方、お店のレジや、印刷を頼んだ順番は、先に並んだ物から先に片付けます。このしまい方をキューと呼びます。

違うのは、出すときに新しい物から出すか、古い物から出すかだけです。この回では、2 つを Python で動かし、元に戻す機能がスタックで作れる理由を確かめます。

皿の山のように上に積み、取るのも一番上からで、積んだ順の逆に出てくる図

スタックとキューはどう違うのか

スタックは後から入れた物が先に出て、キューは先に入れた物が先に出ます。入れる所と出す所が同じ端か、反対の端かの違いです。

スタックは上に積み、上から取る

スタックは、皿の山のように、新しい物を一番上に積み (push、プッシュ)、取るときも一番上から取ります (pop、ポップ)。最後に入れた物が最初に出るので、LIFO (Last In, First Out、後入れ先出し) と呼びます。

Python の公式文書は、list をそのままスタックとして使えると書いています。積むのは append()、取るのは引数なしの pop() で、どちらも list の後ろの端だけを触るので速く済みます。

キューは後ろに並び、前から出る

キューは、窓口の行列のように、新しい物を後ろに加え (enqueue、エンキュー)、出すときは先頭から出します (dequeue、デキュー)。最初に入れた物が最初に出るので、FIFO (First In, First Out、先入れ先出し) と呼びます。

Python の公式文書は、キューに list を使うのは効率がよくないと書いています。先頭から取り出すと、残りの全部を 1 つずつ前へずらす必要があるからです。代わりに、両端から速く出し入れできる collections.deque を使うよう勧めています。

2 つの違いを表で比べる

見る所スタックキュー
出る順新しい物から古い物から
入れるappend(x)append(x)
出すpop()popleft()
次に出る物を見るs[-1]q[0]
Python の型listdeque
出し入れの手間O(1)O(1)

空かどうかは、どちらも if not s で、いくつ入っているかは len(s) で分かります。手間の O(1) は、中にいくつ入っていても、1 回の出し入れの手間が変わらないことを表します。Python の公式文書は、list の後ろへの append を O(1) とし、deque は両端の出し入れをほぼ同じ O(1) でできると書いています。

スタックとキュー

動かして確かめる

1 本目は、元に戻す (undo) とやり直し (redo) を、2 つのスタックで作ります。書くたびに、書く前の文を undo に積みます。元に戻すときは、今の文を redo に積んでから、undo の一番上を取り出します。

動かす 元に戻すとやり直しを 2 つのスタックで

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

書いた  あいう
戻す    あい
戻す    あ
やり直し あい
書いた  あいえ
やり直し あいえ
redo の数 0

「あ」「い」「う」と書いたあと、元に戻すを 2 回押すと「あい」、「あ」と、新しい操作から順に戻ります。やり直すと「あい」に進みます。

ここで新しく「え」と書くと、redo を空にします。戻した先で別の文を書いたので、「う」をやり直す意味が無くなったからです。その後でやり直しを押しても、文は「あいえ」のままで、redo に残った数は 0 です。

元に戻す機能がスタックで作れるのは、戻したいのがいつも一番新しい操作で、それがスタックの一番上にあるからです。キューで作ると、一番古い操作から戻ってしまいます。

2 本目は、かっこの対応をスタックで確かめます。開きかっこが来たら積み、閉じかっこが来たら一番上を取り出して、種類が合うかを見ます。出力は、確かめた文字列と結果で、何字目かは 1 から数えます。

動かす かっこの対応をスタックで確かめる

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

(a[1] + b)  正しい
f(x[0)]     6字目が違う
{(}         3字目が違う
((a)        1個が残る
a)          2字目が余分

(a[1] + b) は正しく閉じています。f(x[0)] は 6 字目の ) で、一番上にあるのが [ なので種類が違います。後から開いたかっこを先に閉じる、という決まりがスタックの順と同じなので、この確かめ方が使えます。((a) は最後に 1 個が閉じずに残り、a) は 2 字目の ) で積んだ物が無く、余分だと分かります。

スタックとキューはどこで崩れるのか

キューを list で作ると取り出すたびに詰め直しが起き、来る数が片付ける数より多いとキューは伸び続けます。

list で作ったキューは、取り出すたびに詰め直す

list の pop(0) で先頭を取り出すと、残りの全部が 1 つずつ前へずれます。Python の公式文書の計算量の表でも、list の pop(k) は O(n − k) で、先頭の pop(0) は O(n) です。

次のコードは、公式文書の説明の通りに、取り出すたびに残りの数だけ詰め直すとして、詰め直した回数を数えます。deque の popleft() は詰め直しが無いので 0 です。

動かす キューを list で作ると詰め直しが増える

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

件数 list deque
1000 499500 0
2000 1999000 0
4000 7998000 0

1000 件を全部取り出すと、list では 499500 回詰め直します。件数が 2 倍の 2000 件では 1999000 回で、約 4 倍です。全部を取り出す手間が、前の回のソートと同じ n² の形になります。deque なら、件数が増えても詰め直しはありません。

キュークラス 先頭を抜いた代償

来る数が多いと、キューは伸び続ける

キューは、来る物が片付ける物より多いと、長さが伸び続けます。先に来た物から片付けるので、待っている物ほど待ち時間が長くなります。

次のコードは、1 刻みごとに 3 つ来て 2 つ片付けるキューを、10 刻み動かします。出力は、刻み、キューの長さ、次に片付ける物 (先頭) が何刻み待ったかです。最後の 2 行は、先に来た順で片付けたときと、後に来た順で片付けたときに、次に片付ける物が何刻み目に来た物かです。

動かす 来る数が多いとキューが伸びる

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

刻み 長さ 先頭の待ち
1 1 0
4 4 1
7 7 2
10 10 3
先に来た順の次 7
後に来た順の次 10

1 刻みで 1 つずつ余るので、10 刻み目には長さが 10 になります。先頭の待ちも 0、1、2、3 と伸び続け、来る数が減らない限り止まりません。

10 刻み目に、先に来た順で片付けると、7 刻み目に来た古い物を処理します。後に来た順 (スタックの順) で片付けると、10 刻み目に来たばかりの物を処理します。混んでいるときに古い物から片付けると、頼んだ人がもう待つのをやめた物に手間を使うことになります。次の実例は、この問題に本番で出会った記録です。

スタックとキューは仕事でどう確かめるのか

仕事では、出す順が「新しい物から」か「古い物から」かを先に決め、Python の型をそれに合わせ、キューの長さを見張ります。

  1. 出す順を決める。元に戻す、ブラウザの戻る、かっこの対応、深く先に進む探し方はスタック。仕事の受付順、印刷の順番、近い順に広げる探し方はキュー
  2. スタックは list の append と pop、キューは collections.deque の append と popleft を使う。list の pop(0) をループの中で使っていないかを探す
  3. 試験では、空から取り出したときの振る舞いを決めておく。Python の list と deque は、空から取り出すと IndexError を出す
  4. 本番では、キューの長さと、先頭が待った時間を見張る。長さが増え続けるなら、来る数が片付ける数を上回っている

元に戻すの試験

def test_undo_returns_newest():
    write("あ")
    write("い")
    do_undo()
    assert text == "あ"

関わる実例

Facebook は、混んだときに新しい要求から片付けた (2015年11月)

Facebook の技術者は、2015年11月号の Communications of the ACM に、障害を減らす工夫をまとめた記事「Fail at Scale」を書きました。記事によると、過去の遅れの障害を調べると、最悪の障害の多くで、大量の要求がキューに並んで処理を待ち、キューは決めた上限まで伸び続けていました。

記事は、対策の 1 つとして adaptive LIFO (状況に合わせた後入れ先出し) を挙げています。多くのサービスはキューを FIFO の順で処理しますが、混んでいるときに一番先に来た要求は、待たされすぎて、頼んだ人がすでに操作をやめていることが多いからです。普段は FIFO で処理し、キューができ始めたら LIFO に切り替えます。あわせて、キューで待つ時間に上限を設ける CoDel (制御された遅れ) という仕組みを使い、長い行列が居座らないようにしています。

崩れた前提は「先に来た物から片付けるのが、いつも一番よい」です。上の 4 本目のコードで見た通り、混んだキューでは、先頭にいるのは古くなった物です。

出典は Fail at Scale (Communications of the ACM、2015年11月号) です。

Amazon は、たまった行列を別のキューへ逃がした (2019年12月5日)

Amazon は2019年12月5日、技術者向けの記事「Avoiding insurmountable queue backlogs」(取り戻せないキューのたまりを避ける) を公開しました。記事は、1 時間止まったシステムが元に戻るには、止まっていた間にたまった分を片付けるため、さらに 1 時間、普段の 2 倍の処理の力が要ると説明しています。

記事によると、利用者は、たまりができたときには新しいデータから先に処理されることを望み、FIFO に近いキューで作ったリアルタイムのシステムでも LIFO に近い振る舞いが好まれます。そこで、取り出した物が古ければ、別のたまり用のキューへ移し、今のキューに追いついてから片付ける方法を紹介しています。

崩れた前提は「キューに入れておけば、いつかは順に片付く」です。来る量が片付ける量を上回ると、キューは伸び続け、古い物を待つ間に新しい物まで遅れます。

出典は Avoiding insurmountable queue backlogs (Amazon Builders' Library) です。

よくある問い

呼び出しのスタックやスタックオーバーフローも同じスタックですか

同じ考え方です。関数を呼ぶと、戻る場所などの記録が積まれ、関数が終わると一番上から取り出されて呼んだ所に戻ります。後から呼んだ関数ほど先に終わるので LIFO です。呼び出しが深くなりすぎて積む場所が尽きるのがスタックオーバーフローで、Python では上限の深さを超えると RecursionError が出ます。

スタックとキューはどちらが速いですか

どちらも、正しい型で作れば 1 回の出し入れは O(1) で、速さに差はほとんどありません。差が出るのは作り方で、list の先頭から取り出すキューは、上のコードの通り件数の 2 乗の形で詰め直しが増えます。

スタックとキューは、どんな場面で使われていますか

スタックは、元に戻す、ブラウザの戻る、かっこの対応、関数の呼び出しに使われます。キューは、仕事の受付順、印刷の順番、ほかの処理に渡すデータの待ち行列に使われます。木やグラフをたどるときは、スタックを使うと深い方へ先に進み、キューを使うと近い方から広げて進みます。

deque と queue.Queue はどう違いますか

collections.deque は両端から速く出し入れできる入れ物で、上限の長さ maxlen を決めると、いっぱいのときに反対の端から古い物を捨てる、輪のような使い方もできます。queue.Queue は、公式文書によると、いくつものスレッド (同時に動く処理の流れ) の間で安全にデータを受け渡すためのキューで、上限に達すると入れるのを待たせます。1 つの処理の中で使うなら deque で十分です。

優先度付きキューとは何ですか

入れた順ではなく、優先度の高い物 (値の小さい物) から先に出すキューです。Python では標準の heapq や queue.PriorityQueue で作れ、heapq の公式文書は、一番小さい物がいつも先頭の heap[0] にあると書いています。

確認クイズ

答えだと思う選択肢を押すと、その場で正誤と理由が開きます。4 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。

1 問目

「あ」「い」「う」の順に打ち込んでから、元に戻すを 1 回押しました。元に戻す機能をスタックで作っているとき、消えるのはどれですか。

2 問目

Python で、先に入れた物から順に取り出すキューを作ります。件数が多いときに一番向いているのはどれですか。

3 問目

かっこの対応 f(x[0)] を、スタックで確かめます。6 字目の ) が来たとき、スタックの一番上には何がありますか。

4 問目

このコードを動かすと何が出ますか。同じ 1、2、3 を、リストのスタックと deque のキューに入れて、出し入れします。

スタックとキューから取り出す

from collections import deque

s = []  # スタック
q = deque()  # キュー
for v in [1, 2, 3]:
    s.append(v)
    q.append(v)
s.pop()
q.popleft()
s.append(4)
q.append(4)
print(s.pop(), q.popleft())

説明課題

元に戻す機能がスタックで作れる理由を、「一番新しい」「一番上」という言葉を使って 3 文以内で説明してください。キューで作るとどうなるかも 1 文入れてください。書いたら、下の模範解答を開いて比べてください。

模範解答

自分の説明を書いてから開いて、比べてください。

この回の先の一歩

元に戻す機能、画面の戻る、仕事の順番待ちは、どれもスタックかキューで作られています。どちらの順で取り出すかを決められると、混んだときの振る舞いまで設計できます。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。

もっと深く

この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。

一次資料

どれも 2026年10月26日に開いて、題と中身を確かめました。

次へ

前の回 2-3クイックソートとマージソート速いソート 2 つ、平均と最悪次の回 2-5再帰自分を呼んで小さくする

道 2 データ構造とアルゴリズムの回

  1. 2-0アルゴリズムとは順次、分岐、反復の 3 つで書く手順頁で読む
  2. 2-1線形探索と二分探索100 万件でも 20 回で見つかる頁で読む
  3. 2-2バブルソートと挿入・選択ソート遅いソート 3 つ、2 倍で約 4 倍頁で読む
  4. 2-3クイックソートとマージソート速いソート 2 つ、平均と最悪頁で読む
  5. 2-4スタックとキュー積む順と並ぶ順この回
  6. 2-5再帰自分を呼んで小さくする頁で読む
  7. 2-6木と二分探索木たどる順、片寄り頁で読む
  8. 2-7ハッシュテーブル鍵から一気に引く、衝突頁で読む
  9. 2-8ダイクストラ法と最短経路点と線、幅優先、重みのある道頁で読む
  10. 2-9動的計画法同じ計算を 2 度しない頁で読む
  11. 2-10試験と面接で確かめる基本情報 科目B、道場 10 問、面接 20 問頁で読む

道 2 の頁へ戻るほかの道を見る