栈与队列栈

栈：先进后出，后进先出。

 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     }

打印结果：
4
3
2
1

栈的应用：分隔符匹配

 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)。也就是说，栈操作所花的时间不依赖与栈中数据项的个数，因此操作时间很短，栈不需要比较和移动操作。

栈与队列 栈

栈与队列栈