數(shù)組、鏈表、樹等數(shù)據(jù)結(jié)構(gòu)適用于存儲數(shù)據(jù)庫應(yīng)用中的數(shù)據(jù)記錄，它們常常用于記錄那些現(xiàn)實世界的對象和活動的數(shù)據(jù)，便與數(shù)據(jù)的訪問：插入、刪除和查找特定數(shù)據(jù)項。

而棧和隊列更多的是作為程序員的工具來使用。他們主要作為構(gòu)思算法的輔助工具，而不是完全的數(shù)據(jù)存儲工具。這些數(shù)據(jù)結(jié)構(gòu)的生命周期比那些數(shù)據(jù)庫類型的結(jié)構(gòu)要短很多。在程序操作執(zhí)行期間它們才被創(chuàng)建，通常它們?nèi)?zhí)行某項特殊的任務(wù)，當任務(wù)完成后就被銷毀。

棧和隊列的訪問是受限制的，即在特定時刻只有一個數(shù)據(jù)項可以被讀取或刪除。

棧和隊列是比數(shù)組和其他數(shù)據(jù)結(jié)構(gòu)更加抽象的結(jié)構(gòu)，是站在更高的層面對數(shù)據(jù)進行組織和維護。

棧的主要機制可用數(shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。優(yōu)先級隊列的內(nèi)部實現(xiàn)可以用數(shù)組或者一種特別的樹——堆來實現(xiàn)。。

先來了解棧的概念和實例，然后分別深入理解隊列和優(yōu)先級隊列。

棧只允許訪問一個數(shù)據(jù)項：即最后插入的數(shù)據(jù)。移除這個數(shù)據(jù)項后才能訪問倒數(shù)第二個插入的數(shù)據(jù)項。它是一種“后進先出”的數(shù)據(jù)結(jié)構(gòu)。

棧最基本的操作是出棧（Pop）、入棧（Push），還有其他擴展操作，如查看棧頂元素，判斷棧是否為空、是否已滿，讀取棧的大小等。

下面我們就用數(shù)組來寫一個棧操作的封裝類。

[java] view plaincopyprint?

1. public class Stack { 
2.       private int size;                 //棧的大小 
3.       private int top;                  //棧頂元素的下標 
4.       private int [] stackArray;   //棧的容器 
5.        
6.       //構(gòu)造函數(shù) 
7.       public Stack(int size){ 
8.              stackArray = new int [size]; 
9.              top = -1; //初始化棧的時候，棧內(nèi)無元素，棧頂下標設(shè)為-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. } 

上例中，沒有對可能的異常進行處理，需要由編程人員保證程序的正確性，比如，才出棧前需要應(yīng)該保證棧中有元素，在入棧前應(yīng)保證棧沒有滿。

                                                                            入棧操作示意圖

                                                                                                           出棧操作示意圖

棧通常用于解析某種類型的文本串。通常，文本串是用計算機語言寫的代碼行，而解析它們的程序就是編譯器。

下面我們來用棧來實現(xiàn)一個經(jīng)典的應(yīng)用：分隔符匹配。想一下在Eclipse編程時，如果我們寫的代碼中如果多了一個“{”，后者少了一個“}”，或者括號的順序錯亂，都會報錯。接下來我們就用棧來模擬這種分隔符匹配。

分隔符匹配程序從字符串中不斷地讀取程序，每次讀取一個字符，若發(fā)現(xiàn)它是左分隔符（{、[、(），將它壓入棧中。當讀到一個右分隔符時 （)、]、}），彈出棧頂元素，并且查看它是否和該右分隔符匹配。如果它們不匹配，則程序報錯。如果到最后一直存在著沒有被匹配的分隔符，程序也報錯。

我們來看下面這個正確的字符串，在棧中的變化過程：

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

所讀字符                  棧中內(nèi)容

      a                                空

      {                                  {

      b                                {

      (                                  {(

      c                                {(

      [                                  {([

      d                                {([

      ]                                  {(

      e                                {(

      )                                  {

      f                                  {

      }                                  空

最后出現(xiàn)的左分隔符需要被最先匹配，這符合棧“后進先出”的規(guī)則。

在本例中，要處理的是字符，所以需要對上面的Stack類進行修改，需要將存放元素的數(shù)組改為char類型，并把相關(guān)方法的參數(shù)類型改為char類型，其余不變。

[java] view plaincopyprint?

1. public class Stack { 
2.       private int size;                 //棧的大小 
3.       private int top;                  //棧頂元素的下標 
4.       private char [] stackArray;       //棧的容器 
5.        
6.       //構(gòu)造函數(shù) 
7.       public Stack(int size){ 
8.              stackArray = new char [size]; 
9.              top = -1; //初始化棧的時候，棧內(nèi)無元素，棧頂下標設(shè)為-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.       //構(gòu)造方法，接受待檢查的字符串 
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.                     //匹配結(jié)束時如果棧中還有元素，證明右分隔符缺失 
51.                     System.out.println("有括號沒有關(guān)閉！"); 
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.