スタックパターン

基本

カテゴリ: stacks

概要

スタックは「後入れ先出し」（LIFO: Last-In-First-Out）の原則に従うデータ構造です。新しい要素は常にスタックの「先頭」（または「上部」）に追加され、要素の削除も先頭からのみ行われます。スタックは、要素の追加（push）と削除（pop）の操作が O(1) の時間で行えるため、特定のアルゴリズムパターンで非常に効果的です。再帰の代替手段としても使用でき、関数呼び出しの管理やバックトラッキングにも利用されます。

コードテンプレート

Java

Python

Stack<Integer> stack = new Stack<>();
stack.push(1);  // 要素の追加
int top = stack.peek();  // 先頭要素の参照
int popped = stack.pop();  // 要素の削除と取得
boolean isEmpty = stack.isEmpty();  // 空かどうかのチェック

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

後入れ先出しLIFO括弧のバランス式の評価履歴追跡元に戻す機能最後に見た要素次の大きい要素前の大きい要素単調スタック深さ優先探索非再帰的実装構文解析コールスタックバックトラッキングネストされた構造

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
有効な括弧（Valid Parentheses）: 括弧の文字列が有効かどうかを判定する
2
ヒストグラムの最大長方形（Largest Rectangle in Histogram）: ヒストグラムの中で最大の長方形の面積を求める
3
毎日の気温（Daily Temperatures）: 各日について、より高い気温になるまでの日数を求める
4
逆ポーランド記法の評価（Evaluate Reverse Polish Notation）: 後置記法で書かれた式を評価する

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

易

有効な括弧

文字列 s が与えられたとき、括弧が有効かどうかを判定する関数を作成してください。有効な括弧とは、開き括弧が同じ種類の閉じ括弧で正しく閉じられ、開き括弧が正しい順序で閉じられることを意味します。 ...

中

最小スタック

スタックの基本操作（push、pop、top）をサポートし、さらに最小要素を定数時間で取得する操作（getMin）をサポートする「MinStack」クラスを設計してください。実装すべきメソッド： ...

難

ヒストグラムの最大長方形

n個の非負整数の配列heightsが与えられます。この配列の各要素heightsは、幅1の棒グラフの高さを表します。ヒストグラム内で形成できる最大の長方形の面積を求めてください。...