JavaでのStack実装
Stackは、LIFO(後入れ先出し)の原則に従う線形データ構造です。つまり、オブジェクトは、トップとも呼ばれるその一端でのみ挿入または削除できます。
Stackは次の操作をサポートします。
- push Stackの一番上(つまり、現在の一番上の要素の上)にアイテムを挿入します。
- pop Stackの最上位にあるオブジェクトを削除し、そのオブジェクトを関数から返します。Stackサイズは1つ減ります。
- isEmpty Stackが空かどうかをテストします。
- isFull Stackがいっぱいかどうかをテストします。
- peek Stackからオブジェクトを削除したり、Stackを変更したりせずに、Stackの最上位にあるオブジェクトを返します。
- size Stackに存在する要素の総数を返します。
アレイを使用したStackの実装
Stackは、アレイとして簡単に実装できます。以下は、アレイを使用したJavaでのStack実装です。
|
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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
class Stack { private int arr[]; private int top; private int capacity; //Stackを初期化するコンストラクタ Stack(int size) { arr = new int[size]; capacity = size; top = -1; } //要素`x`をStackに追加するユーティリティ関数 public void push(int x) { if (isFull()) { System.out.println("Overflow\nProgram Terminated\n"); System.exit(-1); } System.out.println("Inserting " + x); arr[++top] = x; } //Stackから最上位の要素をポップするユーティリティ関数 public int pop() { //Stackのアンダーフローをチェックします if (isEmpty()) { System.out.println("Underflow\nProgram Terminated"); System.exit(-1); } System.out.println("Removing " + peek()); //Stackサイズを1減らし、(オプションで)ポップされた要素を返します return arr[top--]; } //Stackの最上位要素を返すユーティリティ関数 public int peek() { if (!isEmpty()) { return arr[top]; } else { System.exit(-1); } return -1; } //Stackのサイズを返すユーティリティ関数 public int size() { return top + 1; } //Stackが空かどうかをチェックするユーティリティ関数 public boolean isEmpty() { return top == -1; //また return size() == 0; } //Stackがいっぱいかどうかをチェックするユーティリティ関数 public boolean isFull() { return top == capacity - 1; //また return size() == capacity; } } class Main { public static void main (String[] args) { Stack stack = new Stack(3); stack.push(1); //Stackに1を挿入 stack.push(2); //Stackに2を挿入 stack.pop(); //一番上の要素を削除します(2) stack.pop(); //一番上の要素を削除します(1) stack.push(3); //Stackに3を挿入 System.out.println("The top element is " + stack.peek()); System.out.println("The stack size is " + stack.size()); stack.pop(); //一番上の要素を削除します(3) //Stackが空かどうかを確認します if (stack.isEmpty()) { System.out.println("The stack is empty"); } else { System.out.println("The stack is not empty"); } } } |
Output:
Inserting 1
Inserting 2
Removing 2
Removing 1
Inserting 3
The top element is 3
The stack size is 1
Removing 3
The stack is empty
の時間計算量 push(), pop(), peek(), isEmpty(), isFull() と size() 一定です、すなわち、 O(1).
Javaコレクションの使用
Stackも含まれています Javaのコレクション フレームワーク。
|
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 |
import java.util.Stack; class Main { public static void main(String[] args) { Stack<String> stack = new Stack<String>(); stack.push("A"); //`A`をStackに挿入します stack.push("B"); //`B`をStackに挿入します stack.push("C"); //`C`をStackに挿入します stack.push("D"); //`D`をStackに挿入します //Stackの一番上を出力します( `D`) System.out.println("The top element is " + stack.peek()); stack.pop(); //一番上の要素を削除します( `D`) stack.pop(); //次のトップを削除します(`C`) //Stackに存在する要素の総数を返します System.out.println("The stack size is " + stack.size()); //Stackが空かどうかを確認します if (stack.empty()) { System.out.println("The stack is empty"); } else { System.out.println("The stack is not empty"); } } } |
Output:
The top element is D
The stack size is 2
The stack is not empty
こちらも参照: