java数据结构----栈

1.栈，队列，优先级队列是比数组和其它数据结构更加抽象的结构，主要通过接口对栈，队列和优先级队列进行定义，这些接口表明通过他们可以完成的操作，而他们的主要实现机制对用户来说是不可见的，如栈的主要机制可以通过数组来实现，但同时也可以通过链表来实现。栈只允许访问一个数据项，即最后插入的数据项，移除该数据项之后才可以访问倒数第二个数据项，以此类推。

2.栈的代码

 1 package com.cn.stack;
 2 /**
 3  * 利用数组生成的栈，模拟栈操作
 4  * @author Administrator
 5  *
 6  */
 7 public class Stackx {
 8 private int maxsize;
 9 private long[] stackarray;
10 private int top;
11 public Stackx(int size){
12     maxsize = size;
13     stackarray = new long[maxsize];
14     top = -1;
15 }
16 public void push(long j){
17     stackarray[++top] = j;
18 }
19 public long pop(){
20     return stackarray[top --];
21 }
22 public long peek(){
23     return stackarray[top];
24 }
25 public boolean isEmpty(){
26     return (top == -1);
27 }
28 public boolean isFull(){
29     return (top == maxsize - 1);
30 }
31 public int size(){
32     return top+1;
33 }
34 }

3.栈的简单应用（检查表达式括号匹配情况）：

　　3.1.StackC.java

 1 package com.cn.stack;
 2 /**
 3  * 此程序主要利用栈实现了一个匹配操作符的功能
 4  * @author Administrator
 5  *
 6  */
 7 public class StackC {
 8 private int maxsize;
 9 private char[] stackarray;
10 private int top;
11 public StackC(int size){
12     maxsize = size;
13     stackarray = new char[maxsize];
14     top = -1;
15 }
16 public void push(char c){
17     stackarray[++ top] = c;
18 }
19 public char pop(){
20     return stackarray[top --];
21 }
22 public char peek(){
23     return stackarray[top];
24 }
25 public boolean isEmpty(){
26     return (top == -1);
27 }
28 public boolean isFull(){
29     return (top == maxsize - 1);
30 }
31 }

　　3.2.BracketChecker.java

 1 package com.cn.stack;
 2 
 3 public class BracketCheacker {
 4 private String input;
 5 public BracketCheacker(String in){
 6     input = in;
 7 }
 8 public void Cheak(){
 9     int stacksize = input.length();
10     StackC sc = new StackC(stacksize);
11     for (int i = 0; i < stacksize; i++) {
12         char ch = input.charAt(i);
13         switch (ch){
14         case '{':
15         case '[':
16         case '(':
17             sc.push(ch);
18             break;
19         case ')':
20         case ']':
21         case '}':
22             if (!sc.isEmpty()){
23                 char chx = sc.pop();
24                 if ((ch == '{' && chx!='}')||(ch == '[' && chx !=']')||(ch == '(' && chx !=')')){
25                     System.out.println("erro"+ch+"at"+i);
26                 }
27             }else{
28                 System.out.println("error"+ch+"at"+i);
29                 break;
30             }
31         default:
32             break;
33         }
34     }
35     if (!sc.isEmpty()){
36         System.out.println("error,missing right delimiter");
37     }else{
38         System.out.println("the expression passed check");
39     }
40 }
41 }

　　　3.3.BracketTest.java

 1 package com.cn.stack;
 2 
 3 import java.io.BufferedReader;
 4 import java.io.IOException;
 5 import java.io.InputStreamReader;
 6 
 7 public class BracketTest {
 8 public static String getstring(){
 9     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
10     String s = null;
11     try {
12         s = br.readLine();
13     } catch (IOException e) {
14     }
15     return s;
16 }
17 public static void main(String[] args) {
18     while (true){
19         String in = getstring();
20         if (in.length() != 0){
21             BracketCheacker bc = new BracketCheacker(in);
22             bc.Cheak();
23         }
24     }
25 }
26 }

4.栈操作（出入栈）的时间复杂度是O(1),特点：后入先出