程式設計師，你應該知道的數據結構之棧

  • 2019 年 10 月 3 日
  • 筆記

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

實現一個棧

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

入栈示意图
出栈示意图

棧的實現有兩種方式，一種是基於數組實現的，我們叫作順序棧，另一種是基於鏈表實現的，我們叫作鏈式棧。下面是兩種棧的實現程式碼

基於數組的順序棧

/**   * 基於數組的順序棧   */  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();  }

瀏覽器前進、後退功能

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

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

最後

打個小廣告，金九銀十跳槽季，平頭哥給大家整理了一份較全面的 Java 學習資料，歡迎掃碼關注微信公眾號：「平頭哥的技術博文」領取，祝各位升職加薪。
扫码关注

Tags:

VirMach 便宜 VPS