程式設計師，你該知道的資料結構之棧

　　資料結構中的堆疊不要與Java 中的堆疊混淆，他們兩個不是一回事，資料結構中的堆疊是一種受限制的線性表，堆疊具有先進後出、後進先出的特點，因為棧只允許存取最後一個資料項，也就是最後插入的資料項。也許你會有疑問，棧既然有這麼多限制，為什麼不用陣列或鍊錶而使用棧？在開發中，我們有特定的場景，根據特定的場景去選用資料結構，棧的適用場景非常多，例如瀏覽器的前進與後退、字串括號的合法性等，我們使用棧來實現就比較好，因為堆疊相對數組、鍊錶來說對外提供的介面要少很多，介面少了，出錯的機率就減少了，對風險的可控性就提高了。

推薦教學：PHP影片教學

#實作一個棧

　　從棧的定義可以看出，棧主要有兩個操作，一個是新增一條數據，我們叫做入棧，另一個是獲取一條數據，稱為出棧，下面兩張圖是入棧出棧示意圖。

　　棧的實作有兩種方式，一種是基於陣列實作的，我們叫作順序棧，另一種是基於鍊錶實作的，我們叫作鍊式棧。下面是兩個堆疊的實作程式碼

基於陣列的順序堆疊

/**
 * 基于数组的顺序栈
 */
 public class ArrayStack {    // 栈最大容量
    private int maxSzie;    // 存放内容
    private String[] array;    // 栈顶元素
    private int top;    
    public ArrayStack(int size){      
      this.maxSzie = size;        
      this.array = new String[this.maxSzie];        
      this.top = 0;
    }  
      /**
     * 入栈操作
     *
     * @param data 数据
     * @return 0：入栈失败 1：入栈成功
     */
    public int push(String data) {      
      if (top == maxSzie) return 0;
        array[top] = data;
        top++;        
        return 1;
    }    
    /**
     * 出栈操作
     *
     * @return
     */
    public String pop() {     
       if (top == 0) return null;        
       return array[--top];
    }    
    /**
     * 获取栈顶元素
     *
     * @return
     */
    public String peek() {     
       return array[top - 1];
    }    
    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty() {    
        return top == 0;
    }
}

##基於鍊錶的鍊式堆疊

/**
 * 基于链表的链式栈
 */public class LinkStack {    // 始终指向栈的第一个元素
    private Node top = null;    
    /**
     * 压栈
     *
     * @param data
     * @return
     */
    public int push(String data) {
        Node node = new Node(data);        
        if (top == null) {
            top = node;
        } else {
            node.next = top;
            top = node;
        }       
         return 1;
        }   
     /**
     * 出栈
     *
     * @return
     */
    public String pop() {     
       if (top == null) return null;
        String data = top.getData();
        top = top.next;       
         return data;
    }   
     /**
     * 节点信息
     */
    private static class Node {      
      private String data;      
      private Node next;        
      public Node(String data) {        
          this.data = data;          
          this.next = null;
        }       
      public String getData() {          
        return this.data;
        }
    }
}

　　棧的實作比較簡單，因為堆疊涉及的操作不多，主要就入棧和出棧兩個操作。

堆疊的應用

#偵測字串括號的合法性

　　我們有時候需要偵測字串括號的合法性，也就是一個左括號需要符合一個右括號，這個我們可以使用堆疊來實作。我們可以從一個合法的括號來理解為什麼要使用棧？如果括號使用合法，最後一個左括號跟第一個右括號是匹配的，倒數第二個左括號和第二個右括號匹配的，以此類推，這符合我們棧的特性先進後出。

　　假設我們有三種括號：圓括號 ()、方括號 [] 和花括號{}，我們使用堆疊來偵測括號的合法性。我們將左括號全部壓棧，當出現右括號時，我們就進行匹配，這時候有如下三種情況：

　　●棧為空，說明沒有左括號，括號使用不合法

　　●棧中取出來的左括號跟右括號不匹配，括號使用不合法

　　●棧中取出的左括號跟右括號匹配，括號使用暫時合法

　　當整個字串都掃描完成後，偵測堆疊中是否還有值，如果棧為空，則表示括號使用合法，反正，則括號使用不合法。

實作程式碼

public static boolean BracketChecker(String data) {
    char[] chars = data.toCharArray();
    ArrayStack stack = new ArrayStack(chars.length);    
    for (char ch : chars) {
            switch (ch){
                        case '{':            
                        case '[':            
                        case '(':
                                stack.push(ch);                
                                break;            
                         case '}':            
                         case ']':            
                         case ')':             
                                if (!stack.isEmpty()){                 
                                   char ch1 = stack.pop();                    
                                   if ((ch=='}' && ch1 !='{')
                                        ||(ch==']' && ch1 !='[')
                                        ||(ch==')' && ch1 !='(')

                    ){                 
                           return false;
                    }
                }else {    
                           return false;
                }     
                break;            
        default:            
            break;
        }
    }   
    return stack.isEmpty();
}

瀏覽器前進、後退功能

　　我們使用瀏覽器都知道，瀏覽器可以前進、後退功能，瀏覽器的前進後退也符合棧的特點，我們最先訪問的網頁肯定要最後才能倒回去。我們一起來看看棧怎麼實現這個功能？

　　我們需要定義兩個棧，我們將首次訪問的頁面壓棧到第一個棧中，當點擊後退時，從第一個棧中取出資料放入到第二個棧，當點擊前進按鈕時，從第二個棧取出資料放入第一個棧。當第一個棧沒有資料時，表示沒有頁面可以點擊後退了，當第二個棧沒有資料時，表示沒有頁面可以點擊前進了。這樣我們就透過棧實現了瀏覽器前進、後退功能。

以上是程式設計師，你該知道的資料結構之棧的詳細內容。更多資訊請關注PHP中文網其他相關文章！