1、概述

數(shù)組、鏈表、樹等數(shù)據(jù)結(jié)構(gòu)適用于存儲數(shù)據(jù)庫應用中的數(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)。

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

2、實現(xiàn)

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

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

public class Stack {
    private int size;           //棧的大小
    private int top;            //棧頂元素的下標
    private int [] stackArray;  //棧的容器
    
    //構(gòu)造函數(shù)
    public Stack(int size){
        stackArray = new int [size];
        top = -1;   //初始化棧的時候，棧內(nèi)無元素，棧頂下標設(shè)為-1
        this.size = size;
    }
    
    //入棧，同時，棧頂元素的下標加一
    public void push(int elem){
        stackArray[++top] = elem; //插入棧頂
    }
    
    //出棧，刪除棧頂元素，同時，棧頂元素的下標減一
    public int pop(){
        return stackArray[top--]; 
    }
    
    //查看棧頂元素，但不刪除
    public int peek(){
        return stackArray[top];
    }
    
    //判空
    public boolean isEmpty(){
        return (top == -1);
    }
    
    //判滿
    public boolean isFull(){
        return (top == size-1);
    }
    
}

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

入棧操作示意圖：

1.png

出棧操作示意圖：

2.png

3、應用實例

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

下面我們來用棧來實現(xiàn)一個經(jīng)典的應用：分隔符匹配。

想一下在Eclipse編程時，如果我們寫的代碼中如果多了一個“{”，后者少了一個“}”，或者括號的順序錯亂，都會報錯。接下來我們就用棧來模擬這種分隔符匹配。

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

我們來看下面這個正確的字符串：a{b(c[d]e)f}，在棧中的變化過程：

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

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

public class Stack {
    private int size;           //棧的大小
    private int top;            //棧頂元素的下標
    private char [] stackArray; //棧的容器
    
    //構(gòu)造函數(shù)
    public Stack(int size){
        stackArray = new char [size];
        top = -1;   //初始化棧的時候，棧內(nèi)無元素，棧頂下標設(shè)為-1
        this.size = size;
    }
    
    //入棧，同時，棧頂元素的下標加一
    public void push(char elem){
        stackArray[++top] = elem; //插入棧頂
    }
    
    //出棧，刪除棧頂元素，同時，棧頂元素的下標減一
    public char pop(){
        return stackArray[top--]; 
    }
    
    //查看棧頂元素，但不刪除
    public char peek(){
        return stackArray[top];
    }
    
    //判空
    public boolean isEmpty(){
        return (top == -1);
    }
    
    //判滿
    public boolean isFull(){
        return (top == size-1);
    }
    
}
然后寫一個類來封裝分隔符匹配的操作：

public class BrecketChecker {
    
    private String input;  //存儲待檢查的字符串
    
    //構(gòu)造方法，接受待檢查的字符串
    public BrecketChecker(String in){
        this.input = in;
    }
    
    //檢查分隔符匹配的方法
    public void check(){
        int strLength = input.length();
        Stack stack = new Stack(strLength);
        
        for(int i=0;i<strLength;i++){
            
            char ch = input.charAt(i);  //一次獲取串中的單個字符
            
            switch(ch){
                case '{' :
                case '[' :
                case '(' :
                     //如果為左分隔符，壓入棧
                    stack.push(ch); 
                    break;
                case '}' :
                case ']' :
                case ')' :
                    //如果為右分隔符，與棧頂元素進行匹配
                    if(!stack.isEmpty()){
                        char chx = stack.pop();
                        
                        if((ch == '{' && chx != '}')||
                           (ch == '(' && chx != ')')||
                           (ch == '[' && chx != ']')
                        ){
                            System.out.println("匹配出錯！字符："+ch+",下標："+i);
                        }
                    }else{
                        System.out.println("匹配出錯！字符："+ch+",下標："+i);
                    }
                    
                default :
                    break;
            }
            
        }
        
        if(!stack.isEmpty()){
            //匹配結(jié)束時如果棧中還有元素，證明右分隔符缺失
            System.out.println("有括號沒有關(guān)閉！");
        }
    }
    
}

測試類：

public static void main(String[] args) {
        
        System.out.println("輸入需要檢測的字符串：");
        String str = getString();
        BrecketChecker checker = new BrecketChecker(str);
        checker.check();
    }
    
    public static String getString(){
        String str = "";
        try{
            InputStreamReader reader = new InputStreamReader(System.in);
            BufferedReader bReader = new BufferedReader(reader);
            str = bReader.readLine();
        }catch(IOException e){
            e.printStackTrace();
        }
        return str;
    }