スタックとキュー-スタック

スタック:先に入ってから出て、後に入って先に出ます.

 1 public class Stack {

 2 

 3     private int maxSize;

 4     private int[] stackArray;

 5     private int top;

 6     

 7     public Stack(int s){

 8     　　this.maxSize = s;

 9     　　stackArray = new int[maxSize];

10     　　top = -1;

11     }

12     

13     public void push(int d){

14     　　stackArray[++top] = d;

15     }

16     

17     public int pop(){

18     　　return stackArray[top--];

19     }

20     

21     public int peek(){

22     　　return stackArray[top];

23     }

24     

25     public boolean isFull(){

26     　　return top == maxSize-1;

27     }

28     

29     public boolean isEmpty(){

30     　　return top == -1;

31     }

32     

33 }

 1     public static void main(String[] args) {

 2     　　Stack stack = new Stack(5);

 3     　　stack.push(1);

 4     　　stack.push(2);

 5     　　stack.push(3);

 6     　　stack.push(4);

 7     　　while (!stack.isEmpty()) {

 8         　　System.out.println(stack.pop());

 9     　　}

10     }

印刷結果:4321
スタックの適用:区切り記号の一致

 1 class BracketChecker {

 2     private String input;

 3 

 4     public BracketChecker(String s) {

 5     　　this.input = s;

 6     }

 7 

 8     public void check() {

 9     　　int size = input.length();

10     　　Stack stack = new Stack(size);

11     　　for (int i = 0; i < size; i++) {

12         　　char c = input.charAt(i);

13         　　switch (c) {

14         　　　　case '{':

15         　　　　case '[':

16         　　　　case '(':

17         　　　　　　stack.push(c);

18         　　　　　　break;

19         　　　　case '}':

20         　　　　case ']':

21         　　　　case ')':

22         　　　　　　if (!stack.isEmpty()) {

23             　　　　　　char cx = (char) stack.pop();

24             　　　　　　if ((c == '{' && cx != '}') || (c == '[' && cx != ']')

25                 　　　　　　|| (c == '(' && cx != ')')) {

26             　　　　　　System.out.println("Error : " + c + " at " + i);

27             　　　　　　}

28         　　　　　　} else {

29             　　　　　　System.out.println("Error : " + c + " at " + i);

30         　　　　　　}

31         　　　　　　break;

32         　　　　default:

33         　　　　break;

34         　　}

35     　　}

36     　　if (!stack.isEmpty()) {

37         　　System.out.println("Error : missing right delimiter .");

38     　　}

39     }

40 }

1     public static void main(String[] args) {

2     　　String input = "{ab[c](e)}d}";

3     　　BracketChecker checker = new BracketChecker(input);

4     　　checker.check();

5     }

印刷結果:Error:}at 11
スタックの効率:データ項目のスタック入りとスタック出の時間的複雑度はいずれも定数O(1)である.すなわち、スタック操作にかかる時間は、スタック内のデータ項目の個数に依存しないため、操作時間が短く、スタックは比較および移動操作を必要としない.