数据结构之栈

数组、链表、树等数据结构适用于存储数据库应用中的数据记录，它们常常用于记录那些现实世界的对象和活动的数据，便与数据的访问：插入、删除和查找特定数据项。

而栈和队列更多的是作为程序员的工具来使用。他们主要作为构思算法的辅助工具，而不是完全的数据存储工具。这些数据结构的生命周期比那些数据库类型的结构要短很多。在程序操作执行期间它们才被创建，通常它们去执行某项特殊的任务，当任务完成后就被销毁。

栈和队列的访问是受限制的，即在特定时刻只有一个数据项可以被读取或删除。

栈和队列是比数组和其他数据结构更加抽象的结构，是站在更高的层面对数据进行组织和维护。

栈的主要机制可用数组来实现，也可以用链表来实现。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。。

先来了解栈的概念和实例，然后分别深入理解队列和优先级队列。

栈只允许访问一个数据项：即最后插入的数据。移除这个数据项后才能访问倒数第二个插入的数据项。它是一种“后进先出”的数据结构。

栈最基本的操作是出栈（Pop）、入栈（Push），还有其他扩展操作，如查看栈顶元素，判断栈是否为空、是否已满，读取栈的大小等。

下面我们就用数组来写一个栈操作的封装类。

[java] view plaincopyprint?

1. public class Stack { 
2.       private int size;                 //栈的大小 
3.       private int top;                  //栈顶元素的下标 
4.       private int [] stackArray;   //栈的容器 
5.        
6.       //构造函数 
7.       public Stack(int size){ 
8.              stackArray = new int [size]; 
9.              top = -1; //初始化栈的时候，栈内无元素，栈顶下标设为-1 
10.              this.size = size; 
11.       } 
12.        
13.       //入栈，同时，栈顶元素的下标加一 
14.       public void push(int elem){ 
15.              stackArray[++top] = elem; //插入栈顶 
16.       } 
17.        
18.       //出栈，删除栈顶元素，同时，栈顶元素的下标减一 
19.       public int pop(){ 
20.              return stackArray[top--]; 
21.       } 
22.        
23.       //查看栈顶元素，但不删除 
24.       public int peek(){ 
25.              return stackArray[top]; 
26.       } 
27.        
28.       //判空 
29.       public boolean isEmpty(){ 
30.              return (top == -1); 
31.       } 
32.        
33.       //判满 
34.       public boolean isFull(){ 
35.              return (top == size-1); 
36.       } 
37.        
38. } 

上例中，没有对可能的异常进行处理，需要由编程人员保证程序的正确性，比如，才出栈前需要应该保证栈中有元素，在入栈前应保证栈没有满。

                                                                            入栈操作示意图

                                                                                                           出栈操作示意图

栈通常用于解析某种类型的文本串。通常，文本串是用计算机语言写的代码行，而解析它们的程序就是编译器。

下面我们来用栈来实现一个经典的应用：分隔符匹配。想一下在Eclipse编程时，如果我们写的代码中如果多了一个“{”，后者少了一个“}”，或者括号的顺序错乱，都会报错。接下来我们就用栈来模拟这种分隔符匹配。

分隔符匹配程序从字符串中不断地读取程序，每次读取一个字符，若发现它是左分隔符（{、[、(），将它压入栈中。当读到一个右分隔符时 （)、]、}），弹出栈顶元素，并且查看它是否和该右分隔符匹配。如果它们不匹配，则程序报错。如果到最后一直存在着没有被匹配的分隔符，程序也报错。

我们来看下面这个正确的字符串，在栈中的变化过程：

a{b(c[d]e)f}

所读字符                  栈中内容

      a                                空

      {                                  {

      b                                {

      (                                  {(

      c                                {(

      [                                  {([

      d                                {([

      ]                                  {(

      e                                {(

      )                                  {

      f                                  {

      }                                  空

最后出现的左分隔符需要被最先匹配，这符合栈“后进先出”的规则。

在本例中，要处理的是字符，所以需要对上面的Stack类进行修改，需要将存放元素的数组改为char类型，并把相关方法的参数类型改为char类型，其余不变。

[java] view plaincopyprint?

1. public class Stack { 
2.       private int size;                 //栈的大小 
3.       private int top;                  //栈顶元素的下标 
4.       private char [] stackArray;       //栈的容器 
5.        
6.       //构造函数 
7.       public Stack(int size){ 
8.              stackArray = new char [size]; 
9.              top = -1; //初始化栈的时候，栈内无元素，栈顶下标设为-1 
10.              this.size = size; 
11.       } 
12.        
13.       //入栈，同时，栈顶元素的下标加一 
14.       public void push(char elem){ 
15.              stackArray[++top] = elem; //插入栈顶 
16.       } 
17.        
18.       //出栈，删除栈顶元素，同时，栈顶元素的下标减一 
19.       public char pop(){ 
20.              return stackArray[top--]; 
21.       } 
22.        
23.       //查看栈顶元素，但不删除 
24.       public char peek(){ 
25.              return stackArray[top]; 
26.       } 
27.        
28.       //判空 
29.       public boolean isEmpty(){ 
30.              return (top == -1); 
31.       } 
32.        
33.       //判满 
34.       public boolean isFull(){ 
35.              return (top == size-1); 
36.       } 
37.        
38. } 

然后写一个类来封装分隔符匹配的操作：

[java] view plaincopyprint?

1. public class BrecketChecker { 
2.        
3.       private String input;  //存储待检查的字符串 
4.        
5.       //构造方法，接受待检查的字符串 
6.       public BrecketChecker(String in){ 
7.              this.input = in; 
8.       } 
9.        
10.       //检查分隔符匹配的方法 
11.       public void check(){ 
12.              int strLength = input.length(); 
13.              Stack stack = new Stack(strLength); 
14.              
15.              for(int i=0;i<strLength;i++){ 
16.                      
17.                     char ch =input.charAt(i);  //一次获取串中的单个字符 
18.                      
19.                     switch(ch){ 
20.                            case '{' : 
21.                            case '[' : 
22.                            case '(' : 
23.                                    //如果为左分隔符，压入栈 
24.                                   stack.push(ch); 
25.                                   break; 
26.                            case '}' : 
27.                            case ']' : 
28.                            case ')' : 
29.                                   //如果为右分隔符，与栈顶元素进行匹配 
30.                                   if(!stack.isEmpty()){ 
31.                                          charchx = stack.pop(); 
32.                                          
33.                                          if((ch== '{' && chx != '}')|| 
34.                                             (ch == '(' && chx != ')')|| 
35.                                             (ch == '[' && chx != ']') 
36.                                          ){ 
37.                                                 System.out.println("匹配出错！字符："+ch+",下标："+i); 
38.                                          } 
39.                                   }else{ 
40.                                          System.out.println("匹配出错！字符："+ch+",下标："+i); 
41.                                   } 
42.                                    
43.                            default : 
44.                                   break; 
45.                     } 
46.                      
47.              } 
48.              
49.              if(!stack.isEmpty()){ 
50.                     //匹配结束时如果栈中还有元素，证明右分隔符缺失 
51.                     System.out.println("有括号没有关闭！"); 
52.              } 
53.       } 
54.        
55. } 

测试类

[java] view plaincopyprint?

1. public static void main(String[] args) { 
2.              
3.              System.out.println("输入需要检测的字符串："); 
4.              String str = getString(); 
5.              BrecketChecker checker = newBrecketChecker(str); 
6.              checker.check(); 
7.       } 
8.        
9.       public static String getString(){ 
10.              String str = ""; 
11.              try{ 
12.                     InputStreamReader reader =new InputStreamReader(System.in); 
13.                     BufferedReader bReader = newBufferedReader(reader); 
14.                     str = bReader.readLine(); 
15.              }catch(IOException e){ 
16.                     e.printStackTrace(); 
17.              } 
18.              return str; 
19.       } 
20.