edubun
日本語
English한국어EspañolPortuguêsFrançaisDeutschItalianoРусский日本語
ホーム›プログラミング›データ構造

スタック

{[()()]} のかっこが正しく対になっているかを調べるには、スタック1つと、かっこ1つにつき1回、合わせて8回のプッシュとポップがあれば足ります。

後入れ先出し

積み重ねたお皿を考えましょう。きれいなお皿はいちばん上に置き、使うときもいちばん上から取ります。最後に置いたお皿が最初に出ていきます。スタックは、まさにこのルールを持つデータ構造で、このルールを後入れ先出し（LIFO）と言います。主な操作は2つです。プッシュはいちばん上に値を置き、ポップはいちばん上の値を取り除いて返します。多くのスタックには、取り除かずにいちばん上を見るピークもあります。

MITの6.006の講義ノートでは、スタックは列のインターフェースの特別な場合、つまり insert last(x) と delete last() として扱われます。これだけで作り方がわかります。値を動的配列に入れ、配列の末尾をいちばん上とみなせばよいのです。前のユニットで見たように末尾は安上がりなので、プッシュもポップも1ステップです（ときどき写しがあるので償却で）。スタックの大きさは関係ありません。3個の値のスタックでも3百万個の値のスタックでも、ポップは同じ1ステップです。

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5、最後にプッシュしたもの
console.log(stack[stack.length - 1]); // ピーク: 8
console.log(stack.length);          // 2
読み込み中

ドラッグで回転、スクロールまたはピンチで拡大・縮小。

山として描いたスタック。プッシュとポップはいちばん上でしかできません。かっこの文字列を選んで「かっこを調べる」を押し、スタックがつり合っているかどうかを判定する様子を見ましょう。

かっこを調べる

スタックの代表的な使い道は、かっこがつり合っているかを調べることです。どのコードエディターやコンパイラーもこれをしています。文字列を左から右へ読みます。開きかっこ (、[、{ はそれぞれプッシュします。閉じかっこは、スタックのいちばん上にある開きかっこと対にならなければなりません。対になればその開きかっこをポップし、スタックが空か、いちばん上が違う種類なら、その文字列はつり合っていません。最後にスタックは空でなければなりません。空でなければ、閉じられなかった開きかっこがあります。

ラボの文字列を試しましょう。{[()()]} はプッシュ4回とポップ4回の8ステップで、最後にスタックが空になります。([)] は3文字目で失敗します。[ がいちばん上にあるときに ) が来るからです。(() は最後まで読むと ( が1つ残ります。なぜスタックがこの仕事に合うのでしょうか。かっこは入れ子になり、いちばん最近開いたものが最初に閉じなければなりません。それが後入れ先出しです。

スタックが出てくるほかの場所

  • 呼び出しスタック。関数aがbを呼び、bがcを呼ぶと、コンピューターは呼び出しごとに記録をプッシュします。cが戻るとその記録がポップされ、bは止まったところから続けます。無限の再帰はこのスタックをいっぱいにします。これが「スタックオーバーフロー」のエラーです。
  • 元に戻す。エディターは変更のたびにそれをプッシュします。元に戻すと、いちばん最近の変更がポップされて取り消されます。
  • 戻るボタン。ブラウザーは、離れたページを1つずつプッシュします。「戻る」で最後のページがポップされます。
  • 深さ優先探索。アルゴリズムのコースでは、迷路の中で行けるところまで深く進んでから戻るためにスタックを使いました。
背景計算の考え方としてのスタックは、ふつうミュンヘンのフリードリッヒ・L・バウアーとクラウス・ザメルソンにさかのぼるとされます。算術の式を翻訳する方法を研究していた2人は、あとに回した演算を、最後に入れたものが最初に取り出される入れ物にしまい、それをドイツ語で地下室を意味するKellerと呼びました。2人は1957年にこの方法の特許を出願し、アメリカでは1962年に認められました。ほぼ同じころ、RAND研究所のアレン・ニューウェル、クリフ・ショー、ハーバート・サイモンのリスト処理もスタックに頼っていました。彼らのプログラムは再帰だらけだったからです。
  1. スタックはどの順番で値を返しますか？
    • 先入れ先出し
    • 後入れ先出し
    • 小さいものから
    • ランダムな順番
  2. 空から始めます。4をプッシュ、8をプッシュ、5をプッシュ、ポップ、2をプッシュ。いちばん上にあるのは何ですか？
    • 4
    • 8
    • 5
    • 2
  3. その操作の後、スタックには値がいくつありますか？
  4. A、B、Cの順にプッシュし、空になるまでポップします。ポップした値を順に並べましょう。
  5. {[()()]} をかっこの方法で調べるとき、プッシュとポップは合わせて何回ですか？
  6. ([)] を左から調べると、どこで失敗しますか？
    • 最初の ( で
    • [ で
    • ) で
    • 最後の ] で
  7. (() のどこがまちがっていますか？
    • スタックが空のときに閉じかっこが来る
    • 最後に ( が1つスタックに残っている
    • 角かっこが足りない
    • 何もまちがっていない。つり合っている
  8. 1,000個の値を持つスタック（動的配列に保存）からのポップは何ステップですか？
  9. 関数 main が draw を呼び、draw が line を呼びます。line の実行中、呼び出しスタックのいちばん上にある記録はどれですか？
    • main
    • draw
    • line
    • どれもない
  10. バウアーとザメルソンがスタックの方法の特許を出願したのは何年ですか？
    • 1946
    • 1957
    • 1962
    • 1972
ポイント
  • スタックは後入れ先出しです。上にプッシュし、上からポップします。
  • 動的配列の末尾を使えば、プッシュもポップも1ステップずつです。
  • かっこの検査では開きかっこをプッシュし、閉じかっこのたびにポップします。{[()()]} は8ステップです。
  • 呼び出しスタック、元に戻す機能、「戻る」ボタンはどれもスタックです。
このコースの出典 (11)
  • MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
  • lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
  • 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
  • 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
  • MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
  • Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
  • ECMAScript 2025 Language Specification (tc39.es/ecma262)
  • 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
  • Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
  • D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
  • "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).

確認日: 2026-10-18