Stackとは？
定義
オブジェクトの後入れ先出し(LIFO)スタックを表します。これは、ベクトルをスタックとして処理する5つのオペレーションでVectorクラスを拡張します。
通常のpushオペレーションとpopオペレーションが提供されるほか、スタックの先頭の項目でpeek
を行うメソッド、スタックがemptyかどうかを判定するメソッド、スタックから項目をsearchし、先頭から何番目かを見つけるメソッドが提供されています。引用元）https://docs.oracle.com/javase/jp/8/docs/api/java/util/Stack.html
ポイントは後入れ先出しの構造を持っていることです。
後入れ先出しとは、最後に入れたものから取り出す仕組みです。
構造
箱の中にどんどん上積みしていくイメージです。上積みしているので、取り出すときは最後に入れたものから取り出すことになります。
入り口と出口が同じと考えると簡単です。
Push（追加）
Pop（取り出し）
StackよりDequeが推奨
Java6で実装されたDequeがStackよりも推奨されていますので、新しく実装する場合、または置き換え可能な場合はDequeを実装してください。
両端キューは、LIFO (後入れ先出し)スタックとして使用することもできます。.従来の
Stackクラスよりもこのインタフェースを優先して使用してください。引用元）https://docs.oracle.com/javase/jp/8/docs/api/java/util/Deque.html
使い方
追加
ジェネリクスで型を指定して、その型のオブジェクトをpushメソッドで追加します。
|
1 2 3 4 5 6 7 |
Stack<String> stack = new Stack<String>(); stack.push("first"); stack.push("second"); stack.push("third"); |
取り出し
追加されたオブジェクトはpopメソッドで取り出せます。
空の状態でpopするとEmptyStackExceptionがスローされます。
|
1 2 3 4 5 6 7 |
// first, second, thirdの順でStackされている想定 stack.pop(); // third stack.pop(); // second stack.pop(); // first stack.pop(); // EmptyStackException |
検索
一番上（最後）に追加された位置からの番号を取得します。開始は1からです。
存在しない場合は、-1 が取得されます。
|
1 2 3 4 5 |
// first, second, thirdの順でStackされている想定 stack.search("third"); // 1 stack.search("hoge"); // -1 |
確認
peekメソッドを使います。
一番上（最後）に追加されたオブジェクトをスタックから取り出すことなく取得できるため、実行後に削除されません。
スタックが空の時に呼ばれると、EmptyStackException がスローされます。
|
1 2 3 4 5 6 7 |
// first, second, thirdの順でStackされている想定 stack.peek(); // third // スタックが空の場合 stack.peek(); // EmptyStackException |
要素が空か
emptyメソッドを使います。戻り値はbooleanです。
|
1 2 3 |
stack.empty(); |
どういう時に使うのか？
LIFO（後入れ先出し）の仕組みが応用できるケースで使われます。
ブラウザの操作履歴の管理
「戻る」「進む」操作を実装する際に操作履歴として利用できます。
ブラウザの基本的な履歴管理を再現すると以下のような実装例になります。
実装例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
import java.util.Stack; public class BrowserHistory { private final Stack<String> backStack = new Stack<>(); // 戻る履歴 private final Stack<String> forwardStack = new Stack<>(); // 進む履歴 private String currentPage = "Home"; // 現在のページ // ページを開く public void visit(String url) { backStack.push(currentPage); // 現在のページを「戻る」スタックに追加 currentPage = url; // 現在のページを更新 forwardStack.clear(); // 「進む」履歴をクリア System.out.println("Visited: " + currentPage); } // 戻る操作 public void back() { if (!backStack.isEmpty()) { forwardStack.push(currentPage); // 現在のページを「進む」スタックに追加 currentPage = backStack.pop(); // 「戻る」スタックからページを取得 System.out.println("Back to: " + currentPage); return; } System.out.println("No pages in back history."); } // 進む操作 public void forward() { if (!forwardStack.isEmpty()) { backStack.push(currentPage); // 現在のページを「戻る」スタックに追加 currentPage = forwardStack.pop(); // 「進む」スタックからページを取得 System.out.println("Forward to: " + currentPage); return; } System.out.println("No pages in forward history."); } // 現在のページを表示 public void current() { System.out.println("Current Page: " + currentPage); } public static void main(String[] args) { BrowserHistory browser = new BrowserHistory(); browser.visit("Page1"); browser.visit("Page2"); browser.visit("Page3"); browser.back(); browser.back(); browser.forward(); browser.visit("Page4"); browser.back(); browser.forward(); browser.current(); } } |
実行結果
Visited: Page1
Visited: Page2
Visited: Page3
Back to: Page2
Back to: Page1
Forward to: Page2
Visited: Page4
Back to: Page2
Forward to: Page4
Current Page: Page4
動作の説明
visit(String url):- 新しいページを開くと、現在のページが「戻る履歴」に追加され、進む履歴をクリアする。
back():- 「戻る履歴」から1ページ取得して、現在のページを「進む履歴」に追加する。
forward():- 「進む履歴」から1ページ取得して、現在のページを「戻る履歴」に追加する。
current():- 現在のページを表示します。
JSONなどの括弧の整合性チェック
括弧のバランスチェック（例: {[()]} が正しいかを判定）などにも使えます。
以下はパラメータとして渡される括弧をスタックで管理し、逆順に処理して括弧がペアになっているかをチェックする実装例です。
実装例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
import java.util.Stack; public class BracketBalanceChecker { // 括弧のバランスをチェックするメソッド public static boolean isBalanced(String input) { Stack<Character> stack = new Stack<>(); for (char c : input.toCharArray()) { // 開き括弧はスタックにプッシュ if (c == '(' || c == '{' || c == '[') { stack.push(c); } // 閉じ括弧の場合は対応する開き括弧がスタックのトップにあるか確認 if (c == ')' || c == '}' || c == ']') { if (stack.isEmpty()) { return false; // スタックが空なら不正な閉じ括弧 } char top = stack.pop(); if (!isMatchingPair(top, c)) { return false; // 対応する括弧でない場合 } } } // 最後にスタックが空であればバランスが取れている return stack.isEmpty(); } // 開き括弧と閉じ括弧がペアであるかをチェックするヘルパーメソッド private static boolean isMatchingPair(char open, char close) { return (open == '(' && close == ')') || (open == '{' && close == '}') || (open == '[' && close == ']'); } // テスト用メインメソッド public static void main(String[] args) { String[] testCases = { "{[()]}", "{[(])}", "((()))", "[{()}]()", "{[}", "((())", "" }; for (String testCase : testCases) { boolean result = isBalanced(testCase); System.out.println("Input: " + testCase + " -> " + (result ? "Balanced" : "Not Balanced")); } } } |
実行結果
Input: {[()]} -> Balanced
Input: {[(])} -> Not Balanced
Input: ((())) -> Balanced
Input: [{()}]() -> Balanced
Input: {[} -> Not Balanced
Input: ((()) -> Not Balanced
Input: -> Balanced
動作の説明
isBalanced(String input)- 文字列を1文字ずつチェック。
- 開き括弧はスタックにプッシュ。
- 閉じ括弧の場合、スタックのトップと比較して対応するペアがあるか確認。
isMatchingPair(char open, char close)- 開き括弧と閉じ括弧が対応するペアかどうかを判定。
- テストケース
- 括弧が対応しているものは Balanced。
- 括弧のペアが不正なものは Not Balanced。
- 空文字列
""は括弧がないため Balanced と見なす。
まとめ
- StackはLIFO（後入れ先出し）の構造をしており、最後に入れたものから取得する。
- Java6からはDequeが推奨になっている。
- 使い方はシンプルにLIFOの操作性と用語を理解していればOK。
- Stackを使うと実装が楽になる場合は利用しよう。
コメント