在web開發(fā)中的棧是什么

本篇文章給大家分享的是有關(guān)在web開發(fā)中的棧是什么，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

什么是棧

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

勾起一波回憶

棧是這么定義的：

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

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

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

線性表：棧也是一種線性表，前面詳細(xì)介紹過線性表，它表達(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)匹配問題等等。所以棧也是必須掌握的一門數(shù)據(jù)結(jié)構(gòu)。最簡單大家都經(jīng)歷過，你拿一本書上下疊在一起，就是一個(gè)后進(jìn)先出的過程，你可以把它看成一個(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é)構(gòu)設(shè)計(jì)

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

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

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<數(shù)組長度-1。入棧,top++;a[top]=value;

• 如果top==數(shù)組長度-1;棧滿。

pop彈出并返回首位

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

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

其他操作

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

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

package 隊(duì)棧;  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;         }     } }

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

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

• 像數(shù)組那樣在尾部插入刪除。大家都知道鏈表效率低在查詢，而查詢到尾部效率很低，就算用了尾指針，可以解決尾部插入效率，但是依然無法解決刪除效率(刪除需要找到前驅(qū)節(jié)點(diǎn))，還需要雙向鏈表。前面雖然詳細(xì)介紹過雙向鏈表，但是這樣未免太復(fù)雜!

• 所以我們采用帶頭節(jié)點(diǎn)的單鏈表在頭部插入刪除，把頭當(dāng)成棧頂，插入直接在頭節(jié)點(diǎn)后插入，刪除也直接刪除頭節(jié)點(diǎn)后第一個(gè)節(jié)點(diǎn)即可，這樣就可以完美的滿足棧的需求。

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

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

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

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

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

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

push插入

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

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

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

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

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

pop彈出

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

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

其他操作

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

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

package 隊(duì)棧;  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;//頭節(jié)點(diǎn)     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;          }         } }

棧能這么玩

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

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

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

有效字符串需滿足：

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

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

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

示例 :

輸入: "()[]{}"

輸出: true

示例 :

輸入: "([)]"

輸出: false

分析：

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

從單個(gè)括號(hào)對(duì)來說，((,))都是不滿足的，只有()才可滿足，即一左一右。

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

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

• (({[(下一個(gè))消掉成(({[

• (({[(下一個(gè))消掉成(({[

• (({[下一個(gè)]消掉成(({

• (({下一個(gè)}消掉成((

• ((下一個(gè))消掉成(

• (下一個(gè))消掉成 這樣就滿足題意

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

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();   }

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

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最長有效括號(hào)(困難)

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

示例 :

• 輸入: "(()"

• 輸出: 2

• 解釋: 最長有效括號(hào)子串為 "()"

示例 :

• 輸入: ")()())"

• 輸出: 4

• 解釋: 最長有效括號(hào)子串為 "()()"

方案一暴力

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

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

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

public  int longestValidParentheses(String s) {     char str[]=s.toCharArray();//字符數(shù)組     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; }

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

方案二棧優(yōu)化

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

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

• ( ) ( ) ( ( ( ) 最大為前面部分

• ( ( ( ( ( ( ) ( ) ( ) ( ) 最大為后面部分

對(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)超過左括號(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ù)清零重新開始。這樣一直到最后。你可以把它看成臺(tái)階，遇到(就上一個(gè)臺(tái)階并清零該新臺(tái)階，遇到)就下一個(gè)臺(tái)階并且把數(shù)量加到下降后的臺(tái)階上。具體可以看下面圖片模擬的過程：

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

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

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; }

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

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) == '(') {//(將當(dāng)前的        stack.push(i);     } else {       stack.pop();       if (stack.empty()) {         stack.push(i);       } else {//i-stack.peek就是i是出現(xiàn)的總個(gè)數(shù) peek是還沒匹配的個(gè)數(shù)         maxans = Math.max(maxans, i - stack.peek());       }     }   }   return maxans; }

以上就是在web開發(fā)中的棧是什么，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見到或用到的。希望你能通過這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注億速云行業(yè)資訊頻道。