成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

聊一下棧，就后進先出？

作者： bigsai
開發(fā) 前端
棧是一種后進先出的數(shù)據(jù)結(jié)構(gòu)(可以想象生化金字塔的牢房和生化角斗場的狗洞)。棧，簡單而又不簡單，是因為直接學習棧比較容易，但使用棧解決問題很多時候需要巧妙的方法。

 [[394860]]

什么是棧

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

本文著重講解棧數(shù)據(jù)結(jié)構(gòu)的設(shè)計與實現(xiàn)，然后在文末補充兩道棧非常非常經(jīng)典的問題!一定要會!

[[394861]]

勾起一波回憶

棧是這么定義的：

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

稍微介紹一下關(guān)鍵名詞：

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

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

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

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

數(shù)組實現(xiàn)

數(shù)組實現(xiàn)的棧用的比較多，我們經(jīng)常刷題也會用數(shù)組去實現(xiàn)一個簡單的棧去解決簡單的問題。

結(jié)構(gòu)設(shè)計

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

那么初始化函數(shù)代碼為：

  1. private T data[]; 
  2. private int top; 
  3. public seqStack() { 
  4.     data=(T[]) new Object[10]; 
  5.     top=-1; 
  6. } 
  7. public seqStack(int maxsize) 
  8. { 
  9.     data=(T[]) new Object[maxsize]; 
  10.     top=-1; 
  11. } 

push插入

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

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

pop彈出并返回首位

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

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

其他操作

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

數(shù)組實現(xiàn)：

  1. package 隊棧; 
  2.  
  3. public class seqStack<T> { 
  4.  
  5.     private T data[]; 
  6.     private int top; 
  7.     public seqStack() { 
  8.         data=(T[]) new Object[10]; 
  9.         top=-1; 
  10.     } 
  11.     public seqStack(int maxsize) 
  12.     { 
  13.         data=(T[]) new Object[maxsize]; 
  14.         top=-1; 
  15.     } 
  16.     boolean isEmpty() 
  17.     { 
  18.         return top==-1; 
  19.     } 
  20.     int length() 
  21.     { 
  22.         return top+1; 
  23.     } 
  24.  
  25.     boolean push(T value) throws Exception//壓入棧 
  26.     { 
  27.         if(top+1>data.length-1) 
  28.         { 
  29.             throw new Exception("棧已滿"); 
  30.         } 
  31.         else { 
  32.             data[++top]=value; 
  33.             return true; 
  34.         } 
  35.     } 
  36.     T peek() throws Exception//返回棧頂元素不移除 
  37.     { 
  38.         if(!isEmpty()) 
  39.         { 
  40.             return data[top]; 
  41.         } 
  42.         else { 
  43.             throw new Exception("棧為空"); 
  44.         } 
  45.     } 
  46.     T pop() throws Exception 
  47.     { 
  48.         if(isEmpty()) 
  49.         { 
  50.             throw new Exception("棧為空"); 
  51.         } 
  52.         else { 
  53.            return data[top--]; 
  54.         } 
  55.     } 
  56.     public String toString() 
  57.     { 
  58.         if(top==-1) 
  59.         { 
  60.             return ""; 
  61.         } 
  62.         else { 
  63.             String va=""; 
  64.             for(int i=top;i>=0;i--) 
  65.             { 
  66.                 va+=data[i]+"  "; 
  67.             } 
  68.             return va; 
  69.         } 
  70.     } 
  71. } 

鏈表實現(xiàn)

有數(shù)組實現(xiàn)，鏈表當然也能實現(xiàn)。對于棧的設(shè)計，大致可以分為兩種思路：

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

結(jié)構(gòu)設(shè)計

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

鏈表的節(jié)點：

  1. static class node<T> 
  2. { 
  3.     T data; 
  4.     node next; 
  5.     public node() {     
  6.     } 
  7.     public node(T value) 
  8.     { 
  9.         this.data=value; 
  10.     } 
  11. } 

基本結(jié)構(gòu)：

  1. public class lisStack <T>{ 
  2.     int length; 
  3.     node<T> head;//頭節(jié)點 
  4.     public lisStack() { 
  5.         head=new node<>(); 
  6.         length=0; 
  7.     } 
  8.     //其他方法 
  9. } 

push插入

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

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

如果一個節(jié)點team入棧：

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

pop彈出

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

和數(shù)組同樣需要判斷棧是否為空，如果節(jié)點team出棧：head指向team后驅(qū)節(jié)點。

其他操作

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

鏈表實現(xiàn)：

  1. package 隊棧; 
  2.  
  3. public class lisStack <T>{ 
  4.     static class node<T> 
  5.     { 
  6.         T data; 
  7.         node next; 
  8.         public node() {     
  9.         } 
  10.         public node(T value) 
  11.         { 
  12.             this.data=value; 
  13.         } 
  14.     } 
  15.     int length; 
  16.     node<T> head;//頭節(jié)點 
  17.     public lisStack() { 
  18.         head=new node<>(); 
  19.         length=0; 
  20.     } 
  21.     boolean isEmpty() 
  22.     { 
  23.         return head.next==null; 
  24.     } 
  25.     int length() 
  26.     { 
  27.         return length; 
  28.     } 
  29.     public void push(T value) {//近棧 
  30.        node<T> team=new node<T>(value); 
  31.        if(length==0) 
  32.        { 
  33.            head.next=team; 
  34.        } 
  35.        else { 
  36.         team.next=head.next; 
  37.         head.next=team;} 
  38.        length++; 
  39.     } 
  40.     public T peek() throws Exception { 
  41.         if(length==0) {throw new Exception("鏈表為空");} 
  42.         else {//刪除 
  43.             return (T) head.next.data; 
  44.         } 
  45.   } 
  46.     public T pop() throws Exception {//出棧 
  47.       if(length==0) {throw new Exception("鏈表為空");} 
  48.       else {//刪除 
  49.         T value=(T) head.next.data; 
  50.               head.next=head.next.next;//va.next 
  51.               length--; 
  52.               return value; 
  53.             } 
  54.     } 
  55.     public String toString(){ 
  56.         if(length==0) {return "";} 
  57.         else { 
  58.               String va=""; 
  59.             node team=head.next; 
  60.             while(team!=null) 
  61.             { 
  62.                 va+=team.data+" "; 
  63.                 team=team.next; 
  64.             } 
  65.             return va; 
  66.          }     
  67.     } 
  68. } 

棧能這么玩

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

力扣20有效的括號：

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

有效字符串需滿足：

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

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

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

示例 :

輸入: "()[]{}"

輸出: true

示例 :

輸入: "([)]"

輸出: false

分析：

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

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

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

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

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

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

  1. public boolean isValid(String s) { 
  2.      Stack<Character>stack=new Stack<Character>(); 
  3.      for(int i=0;i<s.length();i++) 
  4.      {   
  5.          char te=s.charAt(i); 
  6.          if(te==']') 
  7.          { 
  8.              if(!stack.isEmpty()&&stack.pop()=='[') 
  9.                  continue; 
  10.              else { 
  11.                 return false; 
  12.             } 
  13.          } 
  14.          else if(te=='}') 
  15.          { 
  16.              if(!stack.isEmpty()&&stack.pop()=='{') 
  17.                  continue; 
  18.              else { 
  19.                 return false; 
  20.             } 
  21.          } 
  22.          else if(te==')') 
  23.          { 
  24.              if(!stack.isEmpty()&&stack.pop()=='(') 
  25.                  continue; 
  26.              else { 
  27.                 return false; 
  28.              } 
  29.          } 
  30.          else 
  31.              stack.push(te); 
  32.      } 
  33.      return stack.isEmpty();  
  34.  } 

當然，JDK自帶的棧用起來不快，可以用數(shù)組優(yōu)化：

  1. public boolean isValid(String s) { 
  2.     char a[]=new char[s.length()]; 
  3.     int index=-1; 
  4.      for(int i=0;i<s.length();i++) 
  5.      {   
  6.          char te=s.charAt(i); 
  7.          if(te==']') 
  8.          { 
  9.              if(index>=0&&a[index]=='[') 
  10.                  index--; 
  11.              else { 
  12.                 return false; 
  13.             } 
  14.          } 
  15.          else if(te=='}') 
  16.          { 
  17.              if(index>=0&&a[index]=='{') 
  18.                  index--; 
  19.              else { 
  20.                 return false; 
  21.             } 
  22.          } 
  23.          else if(te==')') 
  24.          { 
  25.              if(index>=0&&a[index]=='(') 
  26.                  index--; 
  27.              else { 
  28.                 return false; 
  29.              } 
  30.          } 
  31.          else 
  32.              a[++index]=te; 
  33.      } 
  34.      return index==-1;  
  35.  } 

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

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

示例 :

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

示例 :

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

方案一暴力

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

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

當然，在具體的實現(xiàn)上，我們用數(shù)組模擬棧，實現(xiàn)代碼為：

  1. public  int longestValidParentheses(String s) { 
  2.     char str[]=s.toCharArray();//字符數(shù)組 
  3.     int max=0; 
  4.     for(int i=0;i<str.length-1;i++) 
  5.     { 
  6.         int index=-1; 
  7.         if(max>=str.length-i) 
  8.             break; 
  9.         for(int j=i;j<str.length;j++) 
  10.         { 
  11.             if(str[j]=='(') 
  12.                 index++; 
  13.             else { 
  14.                 if(index<0) 
  15.                 { 
  16.                     i=j; 
  17.                     break; 
  18.                 } 
  19.                 else { 
  20.                     index--; 
  21.                 } 
  22.             } 
  23.             if(index==-1&&(j-i+1>max)) 
  24.             { 
  25.                 max=j-i+1; 
  26.             } 
  27.         } 
  28.     }    
  29.     return max; 
  30. } 

這個復雜度太高，我們看看如何用棧優(yōu)化。

方案二棧優(yōu)化

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

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

對于這么一次獲取你會發(fā)現(xiàn)不同括號會有些區(qū)別：

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

):右擴號有兩種情況：

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

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

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

仔細看看這張圖，具體實現(xiàn)代碼為：

  1. public static int longestValidParentheses(String s) { 
  2.        int max=0;   
  3.        int value[]=new int[s.length()+1]; 
  4.        int index=0; 
  5.        for(int i=0;i<s.length();i++) 
  6.        { 
  7.            if(s.charAt(i)=='(') 
  8.            { 
  9.                index++; 
  10.                value[index]=0; 
  11.            } 
  12.            else {//")" 
  13.                if(index==0) 
  14.                { 
  15.                    value[0]=0; 
  16.                } 
  17.                else { 
  18.                    value[index-1]+=value[index--]+2;//疊加 
  19.                    if(value[index]>max)//更新 
  20.                        max=value[index]; 
  21.                } 
  22.            } 
  23.        } 
  24.        return max; 
  25. } 

用棧也可以實現(xiàn)，但是效率比數(shù)組略低：

  1. public int longestValidParentheses(String s) { 
  2.   int maxans = 0; 
  3.   Stack<Integer> stack = new Stack<>(); 
  4.   stack.push(-1); 
  5.   for (int i = 0; i < s.length(); i++) { 
  6.     if (s.charAt(i) == '(') {//(將當前的  
  7.       stack.push(i); 
  8.     } else { 
  9.       stack.pop(); 
  10.       if (stack.empty()) { 
  11.         stack.push(i); 
  12.       } else {//i-stack.peek就是i是出現(xiàn)的總個數(shù) peek是還沒匹配的個數(shù) 
  13.         maxans = Math.max(maxans, i - stack.peek()); 
  14.       } 
  15.     } 
  16.   } 
  17.   return maxans; 
  18. } 

總結(jié)

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

 

責任編輯：武曉燕 來源： bigsai
棧數(shù)據(jù)結(jié)構(gòu)
相關(guān)推薦

2021-04-21 14:19:52

javaignalHandle接口

2025-01-10 11:07:28

2021-04-27 07:52:18

SQLNULLOR

2021-05-06 19:50:14

隊列棧機制

2021-01-29 08:32:21

數(shù)據(jù)結(jié)構(gòu)數(shù)組

2023-02-09 08:48:47

Java虛擬機棧

2022-02-08 08:31:52

const關(guān)鍵字C語言

2021-06-30 00:19:43

AOP動態(tài)代理

2021-06-02 21:31:39

Synchronous非公平模式

2021-03-10 00:02:01

Redis

2021-05-31 06:28:35

AutoMapper對象映射器

2021-10-09 18:26:59

二叉樹多叉樹搜索

2021-03-26 00:20:34

NFT區(qū)塊鏈數(shù)據(jù)庫

2021-08-07 07:56:59

Node邏輯對象

2022-02-22 09:33:38

LIFO棧數(shù)據(jù)結(jié)構(gòu)

2019-01-31 07:16:06

2009-08-26 11:30:16

C# Arraylis

2017-05-26 11:00:38

Python算法棧

2021-06-06 12:59:14

實現(xiàn)方式計數(shù)

2021-07-29 07:45:36

linux編程語言
點贊
收藏

51CTO技術(shù)棧公眾號

主站蜘蛛池模板： 成人国产网站 | 欧美午夜在线 | 国产黄色小视频在线观看 | 亚洲免费成人av | 91亚洲精 | 精品国产伦一区二区三区观看方式 | 天天爽夜夜操 | 欧美国产亚洲一区二区 | 91大神在线资源观看无广告 | 国产精品欧美一区二区三区不卡 | 国产精品亚洲一区二区三区在线观看 | 视频一区二区中文字幕日韩 | 日日干日日射 | 精品久久久精品 | 亚洲国产成人精品久久久国产成人一区 | 日韩高清中文字幕 | 午夜激情影院 | 亚洲一区二区中文字幕 | 欧美亚州综合 | 狠狠操电影 | 男女污网站 | 日本一二区视频 | 亚洲国产精品久久久久秋霞不卡 | 久久久女女女女999久久 | 伊人色综合久久天天五月婷 | 91电影院 | 国产精品一二区 | 欧美亚洲视频在线观看 | 青青草网 | 亚洲人成人网 | 国产综合久久久久久鬼色 | 精品久久久久久久 | 免费麻豆视频 | 国产传媒在线播放 | 久草www| 国产1区在线 | 国产一级黄色网 | 久久久久久亚洲精品 | 免费黄色录像片 | 天天天天操 | 久久综合爱 |