棧

棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。

棧又稱為后進(jìn)先出（Last In First Out ）的線性表，簡稱LIFO結(jié)構(gòu)。

棧只對線性表的插入和刪除的位置做了限制，并沒有對元素的進(jìn)出時間做限制，也就是說，在不是所有元素都進(jìn)棧的情況下，事先進(jìn)去的元素也可以出棧，只要保證是棧頂出棧就可以。

棧的順序存儲結(jié)構(gòu)

我們通常將數(shù)組下標(biāo)為0的一端作為棧低，因?yàn)槭自囟即嬖跅５郏兓钚　?br> 我們定義一個top變量用來指示棧頂元素在數(shù)組中的位置。

進(jìn)棧 O(1)

String push(Stack s,SelemType e){
    if(s.top == MAXZIZE -1){ //棧已滿
      return "ERROR";
   }
   s.top = s.top ++;
   s.data[ s.top] = e;
   return "OK"; 
}

出棧 O(1)

String pop(Stack s,SelemType e){
    if(s.top == -1){ //空棧
      return "ERROR";
   }
    e = s.data[ s.top];//e為出棧元素
   s.top = s.top --;
   return "OK"; 
}

兩棧共享空間

先來說說為什么會有這樣的需求？因?yàn)闂Ｓ幸粋€很大的缺陷，就是必須事先確定好數(shù)組的長度，萬一不夠用了，就需要通過編程手段來動態(tài)的擴(kuò)展數(shù)組的代銷，比較麻煩，所以如果存在兩個相同類型的棧，我們可以通過共享空間的的方式來最大限度的利用事先已經(jīng)開辟好的存儲空間。
下面說一下兩棧共享空間的原理：

image.png

我們讓其中一個棧的棧底稱為數(shù)組的起始位置，另外一個棧的棧底稱為數(shù)組的末尾，新數(shù)組長度為n。兩個棧在數(shù)組的兩端，向中間靠攏。top1和top2是棧1和棧2的棧頂指針，只要他們不見面，兩個棧就可以共享存儲空間。
當(dāng)top1等于-1時代表?xiàng)?為空，而當(dāng)top2等于n時，級棧2為空。
當(dāng)top1+1 = top2時為棧滿狀態(tài)

共享空間入棧

String push(Stack s,SelemType e,int stackNumber){
    if(s.top1 +1 == s.top2){ //棧已滿
        return "ERROR";
    }

    if(stackNumber == 1){ //棧1進(jìn)棧
    s.data[s.top1 ++] = e;
    }
 
  if(stackNumber == 2){ //棧2進(jìn)棧
    s.data[s.top2 ++] = e;
    }

  return “OK”
}

共享空間出棧

String pop(Stack s,SelemType e,int stackNumber){
    if(stackNumber == 1){ 
      if(s.top1 == -1)
          return "ERROR";//棧1為空
       e = s.data[s.top1 --] ;
    }
 
  if(stackNumber == 2){ 
    if(s.top2 == MAXSIZE)
          return "ERROR";//棧2為空
        e = s.data[s.top2 ++] ;
    }
  return “OK”
}

使用場景

事實(shí)上，使用這樣的數(shù)據(jù)結(jié)構(gòu)，通常都是當(dāng)兩個梢的空間需求有相反關(guān)系時，也
就是一個棧增長時另一個棧在縮短的情況。就像買賣股票一樣，你買入時，一定是有
一個你不知道的人在做賣出操作 。有人賺錢，就肯定是有人賠錢。這樣使用兩錢共享空間存儲方法才有比較大的意義。否則兩個錢都在不停地增長，那很快就會因枝滿而溢出了。

棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)

鏈棧相對于數(shù)組棧的優(yōu)勢不存在棧滿的情況，而且也不用事先確定棧的大小。

鏈棧進(jìn)棧 O(1)

image.png

String push(stack s,SelemType e){
  Node node = new Node()；
  node.data = e;
  node.next = s.top;//把當(dāng)前棧頂數(shù)據(jù)賦值給當(dāng)前元素的后繼
  s.top = node; //把新的結(jié)點(diǎn)賦值給棧頂
  s.count = s.count ++;//棧的數(shù)量加1
  return “OK”
}

鏈棧出棧 O(1)

image.png

String pop(stack s,SelemType e){
    if(s.count == 0) //空棧
        return "ERROR"
  e = s.top.data;
  Node node = null;
  node= s.top;
  s.top = s.top.next //把棧頂指針向下移動一個位置
  node = null； //釋放空結(jié)點(diǎn)
  s.count = s.count --;//棧的數(shù)量減1
  return “OK”
}

棧的應(yīng)用

遞歸:斐波那契數(shù)列實(shí)現(xiàn)
四則運(yùn)算表達(dá)式求值：仔細(xì)觀察后發(fā)現(xiàn)，括號都是成對出現(xiàn)的，有左括號就一定會有右括號，對于多重括號，最終也是完全嵌套匹配的。這用棧結(jié)構(gòu)正好合適，只有碰到左括號，就將此左括號進(jìn)棧，不管表達(dá)式有多少重括號，反正遇到左括號就進(jìn)棧，而后面出現(xiàn)右括號時，就讓棧頂?shù)淖罄ㄌ柍鰲?。期間讓數(shù)字運(yùn)算，這樣，最終有括號的表達(dá)式從左到右巡查一遍，棧應(yīng)該是由空到有元素，最終再因全部匹配成功后成為空棧的結(jié)果。

逆波蘭算法：后綴表達(dá)式

例子：9+（3-1）*3+10/2如果用后綴表示法應(yīng)該是"9 3 1 - 3 * + 10 2 / +"
規(guī)則：從左到右遍歷表達(dá)式的每個數(shù)字和符號，遇到是數(shù)字就進(jìn)棧，遇到是符號，就將處于棧頂兩個數(shù)字出棧，進(jìn)行運(yùn)算，運(yùn)算結(jié)果進(jìn)錢，一直到最終獲得結(jié)果。

標(biāo)準(zhǔn)正則表達(dá)式轉(zhuǎn)后綴表達(dá)式

規(guī)則：從左到右遍歷中綴表達(dá)式的每個數(shù)字和符號，若是數(shù)字就輸出，即成為后綴表達(dá)式的一部分。若是符號，則判斷其與棧頂符號的優(yōu)先級（左括號由于還未配對故直接進(jìn)棧），是右括號或優(yōu)先級低于棧頂符號(乘除優(yōu)先加減)則棧頂元素依次出棧并輸出，并將當(dāng)前符號進(jìn)棧，一直到最終輸出后綴表達(dá)式為止。

運(yùn)算步驟

1. 將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式(棧用來迸出運(yùn)算的符號)。
2. 將后綴表達(dá)式進(jìn)行運(yùn)算得出結(jié)果(棧用來進(jìn)出運(yùn)算的數(shù)字)。

隊(duì)列

隊(duì)列是只允許在一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作的線性表。
隊(duì)列是一種先進(jìn)先出（First in First Out）的線性表，簡稱FIFO。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭

隊(duì)列的順序存儲結(jié)構(gòu)

順序存儲的隊(duì)列需建立一個大于 n的數(shù)組，并把隊(duì)列的所有元素存儲在數(shù)組的前n個單元，數(shù)組下標(biāo)為 0的一端即是隊(duì)頭。
入列：由于入隊(duì)操作其實(shí)就是在對尾追加一個元素，不需要移動任何元素，因此時間復(fù)雜度為O(1)。
出列：隊(duì)列的所有元素都得向前移動，一保證隊(duì)列的對頭的位置不為空，因此時間復(fù)雜度為O(n)。

循環(huán)隊(duì)列

我們把首尾相接的順序存儲結(jié)構(gòu)隊(duì)列稱為循環(huán)隊(duì)列。

image.png

判斷循環(huán)隊(duì)列滿或空的2中方法

1、設(shè)置一個標(biāo)致變量flag，當(dāng)front == rear，且flag =0時隊(duì)列為空，當(dāng)front == rear，且flag =1時隊(duì)列為滿。
2、當(dāng)front == rear時，隊(duì)列為空，當(dāng)隊(duì)列滿時，我們修改其條件，保留一個元素空間。也就是說。隊(duì)列滿時，數(shù)組中還有一個空閑單元(不允許出現(xiàn)上圖front和rear重合的狀態(tài))。

image.png

由于rear可能比front大，也有可能比front小，所以盡管他們只差一個位置時就是滿的情況，當(dāng)也有可能是相差真正一圈一圈（比如上圖左邊的圖）。假設(shè)隊(duì)列的最大尺寸為QueueSize，那么判斷隊(duì)列滿的公式為：

(rear + 1)%QueueSize == front
計算隊(duì)列長度：
(rear - front + QueueSize ) %QueueSize

入隊(duì)

String EnQueue(Queue Q,QElemType e){
      if(Q.rear + 1) % MAXSIZE == Q.front)//隊(duì)列已滿
             return "ERROR"

     Q.data[Q.rear] = e;
     Q.rear = (Q.rear + 1) % MAXSIZE;//先后移動一個位置 ，若到最后這轉(zhuǎn)到數(shù)組頭部
   return "OK"
}

出隊(duì)

String EnQueue(Queue Q,QElemType e){
      if(Q.rear  == Q.front)//隊(duì)列為空
             return "ERROR"
     e =  Q.data[Q.front];
     Q.front= (Q.front+ 1) % MAXSIZE;//先后移動一個位置 ，若到最后這轉(zhuǎn)到數(shù)組頭部
    return "OK"
}

隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)

隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)，其實(shí)就是線性表的單鏈衰，只不過它只能尾進(jìn)頭出而已，
我們把它簡稱為鏈隊(duì)列。為了操作上的方便，我們將隊(duì)頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn),而隊(duì)尾指針指向終端結(jié)點(diǎn)

入隊(duì)

鏈?zhǔn)疥?duì)列不存在隊(duì)列為滿的狀態(tài)

image.png

String EnQueue(Queue Q,QElemType e){
     Node node = new Node()；
     node.data = e;
     node.next = null
     Q.rear.next = node;//把新節(jié)點(diǎn)賦值給原隊(duì)尾結(jié)點(diǎn)的后繼
     Q.rear = node;//把當(dāng)前的結(jié)點(diǎn)設(shè)置為尾結(jié)點(diǎn)
     return "OK"
}

出隊(duì)

image.png

String EnQueue(Queue Q,QElemType e){
    Node p = new Node()；
    if(Q.front == Q.rear)//隊(duì)列為空
         return "ERROR";
    p = Q.front.next; //將要刪除的結(jié)點(diǎn)賦值給p
    e = p.data;
    Q.front.next = p.next;//將原隊(duì)通結(jié)點(diǎn)的后繼賦值給頭結(jié)點(diǎn)后繼
    if(Q.rear == p){ // 若對頭是對尾。刪除后將rear指向頭結(jié)點(diǎn)
         Q.rear = Q.front;
      }
     p = null；//將刪除的結(jié)點(diǎn)置空
     return "OK"
}

總結(jié)

對于循環(huán)隊(duì)列與鏈隊(duì)列的比較，可以從兩方面來考慮，從時間上，其實(shí)它們的基
本操作都是常數(shù)時間，即都為 0(1) 的，不過循環(huán)隊(duì)列是事先申請好空間，使用期間不釋放，而對于鏈隊(duì)列，每次申請和釋放結(jié)點(diǎn)也會存在一些時間開銷，如果入隊(duì)出隊(duì)頻繁，則兩者還是有細(xì)微差異。對于空間上來說，循環(huán)隊(duì)列必須有一個固定的長度，所以就有了存儲元素個數(shù)和空間浪費(fèi)的問題。而鏈隊(duì)列不存在這個問題，盡管它需要一個指針域， 會產(chǎn)生 些空間上的開銷，但也可以接受 所以在空間上，鏈隊(duì)列更加靈
活。總的來說，在可以確定隊(duì)列長度最大值的情況 ，建議用循環(huán)隊(duì)列，如果你無法
預(yù)估隊(duì)列的長度時，則用鏈隊(duì)列。

棧和隊(duì)列總結(jié)

image.png