棧

棧是限定僅在表尾進行插入和刪除操作的線性表蚓土。

棧又稱為后進先出（Last In First Out ）的線性表稀火，簡稱LIFO結構庇勃。

棧只對線性表的插入和刪除的位置做了限制该园，并沒有對元素的進出時間做限制，也就是說馆铁，在不是所有元素都進棧的情況下，事先進去的元素也可以出棧锅睛，只要保證是棧頂出棧就可以埠巨。

棧的順序存儲結構

我們通常將數(shù)組下標為0的一端作為棧低，因為首元素都存在棧帝现拒，變化最小辣垒。
我們定義一個top變量用來指示棧頂元素在數(shù)組中的位置。

進棧 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"; 
}

兩棧共享空間

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

image.png

我們讓其中一個棧的棧底稱為數(shù)組的起始位置，另外一個棧的棧底稱為數(shù)組的末尾瞧预，新數(shù)組長度為n屎债。兩個棧在數(shù)組的兩端仅政，向中間靠攏。top1和top2是棧1和棧2的棧頂指針扔茅，只要他們不見面已旧，兩個棧就可以共享存儲空間。
當top1等于-1時代表棧1為空召娜，而當top2等于n時运褪，級棧2為空。
當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進棧
    s.data[s.top1 ++] = e;
    }
 
  if(stackNumber == 2){ //棧2進棧
    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ù)據(jù)結構秸讹，通常都是當兩個梢的空間需求有相反關系時，也
就是一個棧增長時另一個棧在縮短的情況雅倒。就像買賣股票一樣璃诀，你買入時，一定是有
一個你不知道的人在做賣出操作 蔑匣。有人賺錢劣欢，就肯定是有人賠錢。這樣使用兩錢共享空間存儲方法才有比較大的意義裁良。否則兩個錢都在不停地增長凿将，那很快就會因枝滿而溢出了。

棧的鏈式存儲結構

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

鏈棧進棧 O(1)

image.png

String push(stack s,SelemType e){
  Node node = new Node()；
  node.data = e;
  node.next = s.top;//把當前棧頂數(shù)據(jù)賦值給當前元素的后繼
  s.top = node; //把新的結點賦值給棧頂
  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侨把； //釋放空結點
  s.count = s.count --;//棧的數(shù)量減1
  return “OK”
}

棧的應用

遞歸:斐波那契數(shù)列實現(xiàn)
四則運算表達式求值：仔細觀察后發(fā)現(xiàn)犀变，括號都是成對出現(xiàn)的，有左括號就一定會有右括號秋柄，對于多重括號获枝，最終也是完全嵌套匹配的。這用棧結構正好合適华匾，只有碰到左括號映琳，就將此左括號進棧，不管表達式有多少重括號蜘拉，反正遇到左括號就進棧萨西，而后面出現(xiàn)右括號時，就讓棧頂?shù)淖罄ㄌ柍鰲Ｐ裥瘛Ｆ陂g讓數(shù)字運算谎脯，這樣，最終有括號的表達式從左到右巡查一遍持寄，棧應該是由空到有元素源梭，最終再因全部匹配成功后成為空棧的結果娱俺。

逆波蘭算法：后綴表達式

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

標準正則表達式轉后綴表達式

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

運算步驟

1. 將中綴表達式轉化為后綴表達式(棧用來迸出運算的符號)。
2. 將后綴表達式進行運算得出結果(棧用來進出運算的數(shù)字)立磁。

隊列

隊列是只允許在一端進行插入操作藤巢、而在另一端進行刪除操作的線性表。
隊列是一種先進先出（First in First Out）的線性表息罗，簡稱FIFO。允許插入的一端稱為隊尾才沧，允許刪除的一端稱為隊頭

隊列的順序存儲結構

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

循環(huán)隊列

我們把首尾相接的順序存儲結構隊列稱為循環(huán)隊列熔掺。

image.png

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

1、設置一個標致變量flag非剃，當front == rear置逻，且flag =0時隊列為空，當front == rear备绽，且flag =1時隊列為滿券坞。
2鬓催、當front == rear時，隊列為空恨锚，當隊列滿時宇驾，我們修改其條件，保留一個元素空間猴伶。也就是說课舍。隊列滿時，數(shù)組中還有一個空閑單元(不允許出現(xiàn)上圖front和rear重合的狀態(tài))蜗顽。

image.png

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

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

入隊

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

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

出隊

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

隊列的鏈式存儲結構

隊列的鏈式存儲結構，其實就是線性表的單鏈衰狸相，只不過它只能尾進頭出而已薛匪，
我們把它簡稱為鏈隊列。為了操作上的方便脓鹃，我們將隊頭指針指向鏈隊列的頭結點,而隊尾指針指向終端結點

入隊

鏈式隊列不存在隊列為滿的狀態(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é)點賦值給原隊尾結點的后繼
     Q.rear = node;//把當前的結點設置為尾結點
     return "OK"
}

出隊

image.png

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

總結

對于循環(huán)隊列與鏈隊列的比較，可以從兩方面來考慮太颤，從時間上苞俘，其實它們的基
本操作都是常數(shù)時間，即都為 0(1) 的龄章，不過循環(huán)隊列是事先申請好空間吃谣，使用期間不釋放，而對于鏈隊列做裙，每次申請和釋放結點也會存在一些時間開銷岗憋，如果入隊出隊頻繁，則兩者還是有細微差異锚贱。對于空間上來說澜驮，循環(huán)隊列必須有一個固定的長度，所以就有了存儲元素個數(shù)和空間浪費的問題惋鸥。而鏈隊列不存在這個問題杂穷，盡管它需要一個指針域悍缠， 會產(chǎn)生 些空間上的開銷，但也可以接受 所以在空間上耐量，鏈隊列更加靈
活飞蚓。總的來說廊蜒，在可以確定隊列長度最大值的情況 趴拧，建議用循環(huán)隊列，如果你無法
預估隊列的長度時山叮，則用鏈隊列著榴。

棧和隊列總結

image.png