[[394860]]

什么是棧

棧在我們日常編碼中遇到的非常多，很多人對棧的接觸可能僅僅局限在 遞歸使用的是棧 和 StackOverflowException，棧是一種后進先出的數據結構(可以想象生化金字塔的牢房和生化角斗場的狗洞)。棧，簡單而又不簡單，是因為直接學習棧比較容易，但使用棧解決問題很多時候需要巧妙的方法。

本文著重講解棧數據結構的設計與實現，然后在文末補充兩道棧非常非常經典的問題!一定要會!

[[394861]]

勾起一波回憶

棧是這么定義的：

棧(stack)又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素;從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

稍微介紹一下關鍵名詞：

運算受限：也就是這個表你不能隨便的刪除插入。只能按照它的規則進行插入刪除。比如棧就只能在一端進行插入和刪除。同樣，隊列也是運算受限，只能在兩頭操作。

線性表：棧也是一種線性表，前面詳細介紹過線性表，它表達的是一種數據的邏輯關系。也就是在棧內各個元素是相鄰的。當然在具體實現上也分數組和鏈表實現，他們的物理存儲結構不同。但是邏輯結構(實現的目的)相同。

棧頂棧底： 這個描述是偏向于邏輯上的內容，因為大家知道數組在末尾插入刪除更容易，而單鏈表通常在頭插入刪除更容易。所以數組可以用末尾做棧頂，而鏈表可以頭做棧頂。

棧的應用： 棧的應用廣泛，比如你的程序執行查看調用堆棧、計算機四則加減運算、算法的非遞歸形式、括號匹配問題等等。所以棧也是必須掌握的一門數據結構。最簡單大家都經歷過，你拿一本書上下疊在一起，就是一個后進先出的過程，你可以把它看成一個棧。下面我們介紹數組實現的棧和鏈表實現的棧。

數組實現

數組實現的棧用的比較多，我們經常刷題也會用數組去實現一個簡單的棧去解決簡單的問題。

結構設計

對于數組來說，我們模擬棧的過程很簡單，因為棧是后進先出，我們很容易在數組的末尾進行插入和刪除。所以我們選定末尾為棧頂。所以對于一個棧所需要的基礎元素是 一個data[]數組和一個top(int)表示棧頂位置。

那么初始化函數代碼為：

private T data[]; 
private int top; 
public seqStack() { 
    data=(T[]) new Object[10]; 
    top=-1; 
} 
public seqStack(int maxsize) 
{ 
    data=(T[]) new Object[maxsize]; 
    top=-1; 
} 

push插入

棧的核心操作之一push()：入棧操作。

• 如果top<數組長度-1。入棧,top++;a[top]=value;
• 如果top==數組長度-1;棧滿。

pop彈出并返回首位

如果top>=0,棧不為空，可以彈出。return data[top--];

如下圖，本來棧為1,2,3,4,5,6(棧頂),執行pop操作,top變為3的位置并且返回4;

其他操作

例如peek操作時返回棧頂不彈出.所以只需滿足要求時候return data[top]即可。

數組實現：

package 隊棧; 
 
public class seqStack<T> { 
 
    private T data[]; 
    private int top; 
    public seqStack() { 
        data=(T[]) new Object[10]; 
        top=-1; 
    } 
    public seqStack(int maxsize) 
    { 
        data=(T[]) new Object[maxsize]; 
        top=-1; 
    } 
    boolean isEmpty() 
    { 
        return top==-1; 
    } 
    int length() 
    { 
        return top+1; 
    } 
 
    boolean push(T value) throws Exception//壓入棧 
    { 
        if(top+1>data.length-1) 
        { 
            throw new Exception("棧已滿"); 
        } 
        else { 
            data[++top]=value; 
            return true; 
        } 
    } 
    T peek() throws Exception//返回棧頂元素不移除 
    { 
        if(!isEmpty()) 
        { 
            return data[top]; 
        } 
        else { 
            throw new Exception("棧為空"); 
        } 
    } 
    T pop() throws Exception 
    { 
        if(isEmpty()) 
        { 
            throw new Exception("棧為空"); 
        } 
        else { 
           return data[top--]; 
        } 
    } 
    public String toString() 
    { 
        if(top==-1) 
        { 
            return ""; 
        } 
        else { 
            String va=""; 
            for(int i=top;i>=0;i--) 
            { 
                va+=data[i]+"  "; 
            } 
            return va; 
        } 
    } 
} 

鏈表實現

有數組實現，鏈表當然也能實現。對于棧的設計，大致可以分為兩種思路：

• 像數組那樣在尾部插入刪除。大家都知道鏈表效率低在查詢，而查詢到尾部效率很低，就算用了尾指針，可以解決尾部插入效率，但是依然無法解決刪除效率(刪除需要找到前驅節點)，還需要雙向鏈表。前面雖然詳細介紹過雙向鏈表，但是這樣未免太復雜!
• 所以我們采用帶頭節點的單鏈表在頭部插入刪除，把頭當成棧頂，插入直接在頭節點后插入，刪除也直接刪除頭節點后第一個節點即可，這樣就可以完美的滿足棧的需求。

結構設計

設計上和鏈表很相似，長話短說，短話不說，直接上代碼就懂。

鏈表的節點：

static class node<T> 
{ 
    T data; 
    node next; 
    public node() {     
    } 
    public node(T value) 
    { 
        this.data=value; 
    } 
} 

基本結構：

public class lisStack <T>{ 
    int length; 
    node<T> head;//頭節點 
    public lisStack() { 
        head=new node<>(); 
        length=0; 
    } 
    //其他方法 
} 

push插入

與單鏈表頭插入一致，如果不太了解可以看看前面寫的線性表有具體講解過程。

和數組形成的棧有個區別，鏈式實現的棧理論上棧沒有大小限制(不突破內存系統限制)，不需要考慮是否越界，而數組則需要考慮容量問題。

如果一個節點team入棧：

• 空鏈表入棧head.next=team;
• 非空入棧team.next=head.next;head.next=team;

pop彈出

與單鏈表頭刪除一致，如果不太了解請先看筆者對線性表介紹的。

和數組同樣需要判斷棧是否為空，如果節點team出棧：head指向team后驅節點。

其他操作

其他例如peek操作時返回棧頂不彈出.所以只需判空滿足題意時候return head.next.data即可。而length你可以遍歷鏈表返回長度，也可以動態設置(本文采取)跟隨棧長變化。

鏈表實現：

package 隊棧; 
 
public class lisStack <T>{ 
    static class node<T> 
    { 
        T data; 
        node next; 
        public node() {     
        } 
        public node(T value) 
        { 
            this.data=value; 
        } 
    } 
    int length; 
    node<T> head;//頭節點 
    public lisStack() { 
        head=new node<>(); 
        length=0; 
    } 
    boolean isEmpty() 
    { 
        return head.next==null; 
    } 
    int length() 
    { 
        return length; 
    } 
    public void push(T value) {//近棧 
       node<T> team=new node<T>(value); 
       if(length==0) 
       { 
           head.next=team; 
       } 
       else { 
        team.next=head.next; 
        head.next=team;} 
       length++; 
    } 
    public T peek() throws Exception { 
        if(length==0) {throw new Exception("鏈表為空");} 
        else {//刪除 
            return (T) head.next.data; 
        } 
  } 
    public T pop() throws Exception {//出棧 
      if(length==0) {throw new Exception("鏈表為空");} 
      else {//刪除 
        T value=(T) head.next.data; 
              head.next=head.next.next;//va.next 
              length--; 
              return value; 
            } 
    } 
    public String toString(){ 
        if(length==0) {return "";} 
        else { 
              String va=""; 
            node team=head.next; 
            while(team!=null) 
            { 
                va+=team.data+" "; 
                team=team.next; 
            } 
            return va; 
         }     
    } 
} 

棧能這么玩

既然上面詳細講解設計棧，這里來兩道棧非常經典非常經典的例題(非常高頻，很容易忘，又很重要，普通問題就不放的)

力扣20有效的括號：

題意：給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。

左括號必須以正確的順序閉合。

注意空字符串可被認為是有效字符串。

示例 :

輸入: "()[]{}"

輸出: true

示例 :

輸入: "([)]"

輸出: false

分析：

括號類的問題是經典棧類問題，肯定要想到用棧處理。判斷一個字符串滿不滿足一個有效的字符串，就要看它是不是都能組成對。

從單個括號對來說，((,))都是不滿足的，只有()才可滿足，即一左一右。

從多個括號對來說 {[(字符串還可接受任意無限(，[,{的括號。但是如果向左的括號只能先接收)括號(變成{[)。

從上面可以看作一種相消除的思想。例如(({[()()]}))字符串遍歷時候可以這樣處理：

• (({[(下一個)消掉成(({[
• (({[(下一個)消掉成(({[
• (({[下一個]消掉成(({
• (({下一個}消掉成((
• ((下一個)消掉成(
• (下一個)消掉成 這樣就滿足題意

每次操作的時候都判斷剩余有效括號最頂部那個括號是否能夠和遍歷的相消除，這個過程利用棧判斷當前是加入棧還是消除頂部，到最后如果棧為空說明滿足，否則不滿足，當然具體括號要對應，具體實現代碼為：

public boolean isValid(String s) { 
     Stack<Character>stack=new Stack<Character>(); 
     for(int i=0;i<s.length();i++) 
     {   
         char te=s.charAt(i); 
         if(te==']') 
         { 
             if(!stack.isEmpty()&&stack.pop()=='[') 
                 continue; 
             else { 
                return false; 
            } 
         } 
         else if(te=='}') 
         { 
             if(!stack.isEmpty()&&stack.pop()=='{') 
                 continue; 
             else { 
                return false; 
            } 
         } 
         else if(te==')') 
         { 
             if(!stack.isEmpty()&&stack.pop()=='(') 
                 continue; 
             else { 
                return false; 
             } 
         } 
         else 
             stack.push(te); 
     } 
     return stack.isEmpty();  
 } 

當然，JDK自帶的棧用起來不快，可以用數組優化：

public boolean isValid(String s) { 
    char a[]=new char[s.length()]; 
    int index=-1; 
     for(int i=0;i<s.length();i++) 
     {   
         char te=s.charAt(i); 
         if(te==']') 
         { 
             if(index>=0&&a[index]=='[') 
                 index--; 
             else { 
                return false; 
            } 
         } 
         else if(te=='}') 
         { 
             if(index>=0&&a[index]=='{') 
                 index--; 
             else { 
                return false; 
            } 
         } 
         else if(te==')') 
         { 
             if(index>=0&&a[index]=='(') 
                 index--; 
             else { 
                return false; 
             } 
         } 
         else 
             a[++index]=te; 
     } 
     return index==-1;  
 } 

力扣32最長有效括號(困難)

題目描述：給定一個只包含 '(' 和 ')' 的字符串，找出最長的包含有效括號的子串的長度。

示例 :

• 輸入: "(()"
• 輸出: 2
• 解釋: 最長有效括號子串為 "()"

示例 :

• 輸入: ")()())"
• 輸出: 4
• 解釋: 最長有效括號子串為 "()()"

方案一暴力

這種題核心思想就是使用棧模擬。本題的話更簡單一點因為只有(和)兩種括號，使用暴力的時候就可以循環每次找到最長的有效括號。而括號匹配的時候可以直接終止的情況是)右括號多出無法匹配。

例如())(到第三個不可能和前面相連。如果來(只需要期待后面能夠來)，一個)可以和一個(組成一對，消除棧中的一個(。

當然，在具體的實現上，我們用數組模擬棧，實現代碼為：

public  int longestValidParentheses(String s) { 
    char str[]=s.toCharArray();//字符數組 
    int max=0; 
    for(int i=0;i<str.length-1;i++) 
    { 
        int index=-1; 
        if(max>=str.length-i) 
            break; 
        for(int j=i;j<str.length;j++) 
        { 
            if(str[j]=='(') 
                index++; 
            else { 
                if(index<0) 
                { 
                    i=j; 
                    break; 
                } 
                else { 
                    index--; 
                } 
            } 
            if(index==-1&&(j-i+1>max)) 
            { 
                max=j-i+1; 
            } 
        } 
    }    
    return max; 
} 

這個復雜度太高，我們看看如何用棧優化。

方案二棧優化

如何將這道題從一個O(n2)的時間復雜度優化到O(n)?很容易， 我們需要注意他的過程。我們先隨便看幾個可能的最大情況。

• ( ) ) ( ) ( ( ) ( ) ) 最大為后面部分(空格分開)
• ( ) ( ) ( ( ( ) 最大為前面部分
• ( ( ( ( ( ( ) ( ) ( ) ( ) 最大為后面部分

對于這么一次獲取你會發現不同括號會有些區別：

(：左括號一旦出現那么他就期待一個)進行匹配，但它的后面可能有)并且在這中間有很多其他括號對。

):右擴號有兩種情況：

• 一種是當前已經超過左括號前面已經不可能連續了。例如( ) ) ( )第三個括號出現已經使得整個串串不可能連續，最大要么在其左面，要么在其右面。 你可以理解其為一種清零初始機制。
• 另一種情況)就是目標棧中存在(可與其進行匹配。匹配之后要疊加到消除后平級的數量上，并且判斷是否是最大值。(下面會解釋)

在具體實現的思路上，就是使用一個int數組標記當前層級(棧深)有正確的括號數量。模擬一次棧行為從左向右，遇到)太多(當前棧中不存在(進行匹配)就將數據清零重新開始。這樣一直到最后。你可以把它看成臺階，遇到(就上一個臺階并清零該新臺階，遇到)就下一個臺階并且把數量加到下降后的臺階上。具體可以看下面圖片模擬的過程：

( ) ( ( ) ( ) ( ( ) ) )

仔細看看這張圖，具體實現代碼為：

public static int longestValidParentheses(String s) { 
       int max=0;   
       int value[]=new int[s.length()+1]; 
       int index=0; 
       for(int i=0;i<s.length();i++) 
       { 
           if(s.charAt(i)=='(') 
           { 
               index++; 
               value[index]=0; 
           } 
           else {//")" 
               if(index==0) 
               { 
                   value[0]=0; 
               } 
               else { 
                   value[index-1]+=value[index--]+2;//疊加 
                   if(value[index]>max)//更新 
                       max=value[index]; 
               } 
           } 
       } 
       return max; 
} 

用棧也可以實現，但是效率比數組略低：

public int longestValidParentheses(String s) { 
  int maxans = 0; 
  Stack<Integer> stack = new Stack<>(); 
  stack.push(-1); 
  for (int i = 0; i < s.length(); i++) { 
    if (s.charAt(i) == '(') {//(將當前的  
      stack.push(i); 
    } else { 
      stack.pop(); 
      if (stack.empty()) { 
        stack.push(i); 
      } else {//i-stack.peek就是i是出現的總個數 peek是還沒匹配的個數 
        maxans = Math.max(maxans, i - stack.peek()); 
      } 
    } 
  } 
  return maxans; 
} 

總結

到這里，本文對棧的介紹就結束了，相信你可以手寫個棧并且可以小試牛刀解決括號匹配問題!當然棧能解決的問題還有很多比如接雨水問題、二叉樹非遞歸遍歷等等，有些重要的還會再總結。