自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

聊一下棧,就后進(jìn)先出?

開(kāi)發(fā) 前端
棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)(可以想象生化金字塔的牢房和生化角斗場(chǎng)的狗洞)。棧,簡(jiǎn)單而又不簡(jiǎn)單,是因?yàn)橹苯訉W(xué)習(xí)棧比較容易,但使用棧解決問(wèn)題很多時(shí)候需要巧妙的方法。

 [[394860]]

什么是棧

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

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

[[394861]]

勾起一波回憶

棧是這么定義的:

棧(stack)又名堆棧,它是一種運(yùn)算受限的線(xiàn)性表。限定僅在表尾進(jìn)行插入和刪除操作的線(xiàn)性表。這一端被稱(chēng)為棧頂,相對(duì)地,把另一端稱(chēng)為棧底。向一個(gè)棧插入新元素又稱(chēng)作進(jìn)棧、入?;驂簵#前研略胤诺綏m斣氐纳厦?,使之成為新的棧頂元素;從一個(gè)棧刪除元素又稱(chēng)作出?;蛲藯?,它是把棧頂元素刪除掉,使其相鄰的元素成為新的棧頂元素。

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

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

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

棧頂棧底: 這個(gè)描述是偏向于邏輯上的內(nèi)容,因?yàn)榇蠹抑罃?shù)組在末尾插入刪除更容易,而單鏈表通常在頭插入刪除更容易。所以數(shù)組可以用末尾做棧頂,而鏈表可以頭做棧頂。

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

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

數(shù)組實(shí)現(xiàn)的棧用的比較多,我們經(jīng)常刷題也會(huì)用數(shù)組去實(shí)現(xiàn)一個(gè)簡(jiǎn)單的棧去解決簡(jiǎn)單的問(wèn)題。

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

對(duì)于數(shù)組來(lái)說(shuō),我們模擬棧的過(guò)程很簡(jiǎn)單,因?yàn)闂J呛筮M(jìn)先出,我們很容易在數(shù)組的末尾進(jìn)行插入和刪除。所以我們選定末尾為棧頂。所以對(duì)于一個(gè)棧所需要的基礎(chǔ)元素是 一個(gè)data[]數(shù)組和一個(gè)top(int)表示棧頂位置。

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

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

push插入

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

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

pop彈出并返回首位

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

如下圖,本來(lái)?xiàng)?,2,3,4,5,6(棧頂),執(zhí)行pop操作,top變?yōu)?的位置并且返回4;

其他操作

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

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

  1. package 隊(duì)棧; 
  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("棧已滿(mǎn)"); 
  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.     } 

鏈表實(shí)現(xiàn)

有數(shù)組實(shí)現(xiàn),鏈表當(dāng)然也能實(shí)現(xiàn)。對(duì)于棧的設(shè)計(jì),大致可以分為兩種思路:

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

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

設(shè)計(jì)上和鏈表很相似,長(zhǎng)話(huà)短說(shuō),短話(huà)不說(shuō),直接上代碼就懂。

鏈表的節(jié)點(diǎn):

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

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

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

push插入

與單鏈表頭插入一致,如果不太了解可以看看前面寫(xiě)的線(xiàn)性表有具體講解過(guò)程。

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

如果一個(gè)節(jié)點(diǎn)team入棧:

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

pop彈出

與單鏈表頭刪除一致,如果不太了解請(qǐng)先看筆者對(duì)線(xiàn)性表介紹的。

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

其他操作

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

鏈表實(shí)現(xiàn):

  1. package 隊(duì)棧; 
  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é)點(diǎn) 
  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.     } 

棧能這么玩

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

力扣20有效的括號(hào):

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

有效字符串需滿(mǎn)足:

左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。

左括號(hào)必須以正確的順序閉合。

注意空字符串可被認(rèn)為是有效字符串。

示例 :

輸入: "()[]{}"

輸出: true

示例 :

輸入: "([)]"

輸出: false

分析:

括號(hào)類(lèi)的問(wèn)題是經(jīng)典棧類(lèi)問(wèn)題,肯定要想到用棧處理。判斷一個(gè)字符串滿(mǎn)不滿(mǎn)足一個(gè)有效的字符串,就要看它是不是都能組成對(duì)。

從單個(gè)括號(hào)對(duì)來(lái)說(shuō),((,))都是不滿(mǎn)足的,只有()才可滿(mǎn)足,即一左一右。

從多個(gè)括號(hào)對(duì)來(lái)說(shuō) {[(字符串還可接受任意無(wú)限(,[,{的括號(hào)。但是如果向左的括號(hào)只能先接收)括號(hào)(變成{[)。

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

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

每次操作的時(shí)候都判斷剩余有效括號(hào)最頂部那個(gè)括號(hào)是否能夠和遍歷的相消除,這個(gè)過(guò)程利用棧判斷當(dāng)前是加入棧還是消除頂部,到最后如果棧為空說(shuō)明滿(mǎn)足,否則不滿(mǎn)足,當(dāng)然具體括號(hào)要對(duì)應(yīng),具體實(shí)現(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.  } 

當(dāng)然,JDK自帶的棧用起來(lái)不快,可以用數(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最長(zhǎng)有效括號(hào)(困難)

題目描述:給定一個(gè)只包含 '(' 和 ')' 的字符串,找出最長(zhǎng)的包含有效括號(hào)的子串的長(zhǎng)度。

示例 :

  • 輸入: "(()"
  • 輸出: 2
  • 解釋: 最長(zhǎng)有效括號(hào)子串為 "()"

示例 :

  • 輸入: ")()())"
  • 輸出: 4
  • 解釋: 最長(zhǎng)有效括號(hào)子串為 "()()"

方案一暴力

這種題核心思想就是使用棧模擬。本題的話(huà)更簡(jiǎn)單一點(diǎn)因?yàn)橹挥?和)兩種括號(hào),使用暴力的時(shí)候就可以循環(huán)每次找到最長(zhǎng)的有效括號(hào)。而括號(hào)匹配的時(shí)候可以直接終止的情況是)右括號(hào)多出無(wú)法匹配。

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

當(dāng)然,在具體的實(shí)現(xiàn)上,我們用數(shù)組模擬棧,實(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

這個(gè)復(fù)雜度太高,我們看看如何用棧優(yōu)化。

方案二棧優(yōu)化

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

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

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

(:左括號(hào)一旦出現(xiàn)那么他就期待一個(gè))進(jìn)行匹配,但它的后面可能有)并且在這中間有很多其他括號(hào)對(duì)。

):右擴(kuò)號(hào)有兩種情況:

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

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

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

仔細(xì)看看這張圖,具體實(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

用棧也可以實(shí)現(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) == '(') {//(將當(dāng)前的  
  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)的總個(gè)數(shù) peek是還沒(méi)匹配的個(gè)數(shù) 
  13.         maxans = Math.max(maxans, i - stack.peek()); 
  14.       } 
  15.     } 
  16.   } 
  17.   return maxans; 

總結(jié)

到這里,本文對(duì)棧的介紹就結(jié)束了,相信你可以手寫(xiě)個(gè)棧并且可以小試牛刀解決括號(hào)匹配問(wèn)題!當(dāng)然棧能解決的問(wèn)題還有很多比如接雨水問(wèn)題、二叉樹(shù)非遞歸遍歷等等,有些重要的還會(huì)再總結(jié)。

 

責(zé)任編輯:武曉燕 來(lái)源: bigsai
相關(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

隊(duì)列機(jī)制

2021-01-29 08:32:21

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

2023-02-09 08:48:47

Java虛擬機(jī)

2022-02-08 08:31:52

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

2021-06-30 00:19:43

AOP動(dòng)態(tài)代理

2021-06-02 21:31:39

Synchronous非公平模式

2021-05-31 06:28:35

AutoMapper對(duì)象映射器

2021-03-10 00:02:01

Redis

2021-10-09 18:26:59

二叉樹(shù)多叉樹(shù)搜索

2021-03-26 00:20:34

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

2021-08-07 07:56:59

Node邏輯對(duì)象

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-07-28 07:53:13

Linux 棧操作Linux 系統(tǒng)

2021-06-06 12:59:14

實(shí)現(xiàn)方式計(jì)數(shù)
點(diǎn)贊
收藏

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