什麼是棧

百度百科

上，棧是這麼定義的：

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

稍微介紹一下關鍵名詞：

運算受限：也就是這個表你不能随便的删除插入。隻能按照它的規則進行插入删除。比如棧就隻能在一端就行插入和删除。同樣，隊列也是運算受限，隻能在兩天操作。
線性表：棧也是一種線性表，前面詳細介紹過線性表，它表達的是一種資料的邏輯關系。也就是在棧内各個元素是相鄰的。當然在具體實作上也分 數組和連結清單實作 ，他們的實體存儲結構不同。但是邏輯結構( 實作的目的 )相同。
棧頂棧底：這個描述是偏向于邏輯上的内容，因為大家知道 數組在末尾插入删除 更容易，而 單連結清單通常在頭插入删除 更容易。是以數組可以用末尾做棧頂，而連結清單可以頭做棧頂。

棧的應用：

棧的應用廣泛，比如你的程式執行檢視調用堆棧、加減運算、甚至在搜尋算法中dfs，替代遞歸等等。是以棧也是必須掌握的一門資料結構。很多規範也是棧，比如上圖放書拿書一樣！

設計與介紹

這裡我們介紹數組實作的棧和連結清單實作的棧。

數組實作

結構設計

對于數組來說，我們模拟棧的過程很簡單，因為棧是 後進先出 ，我們很容易在數組的末尾進行插入和删除。是以我們標明 末尾為棧頂 。是以對于一個棧所需要的基礎元素是一個data數組和一個top(int)表示棧頂位置。
那麼初始化以及構造的函數代碼為：

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<數組長度-1。入棧。 top++;a[top]=value;
如果top==數組長度-1；棧滿。

pop彈出并傳回首位

如果top>=0,棧不為空，可以彈出。 return data[top--];
如下圖，本來棧為1，2，3，4（棧頂），執行pop操作。top變為3的位置并且傳回4；

其他操作

其他例如peek操作時傳回棧頂 不彈出 .是以隻需滿足題意時候 return data[top] 即可。

連結清單實作

有數組實作，連結清單當然也能實作。對于棧的運算。大緻可以分為兩種思路：

像數組那樣在尾部插入删除。大家都知道連結清單效率 低在查詢 。而查詢到尾部效率很低。而我們就算用了尾指針，可以解決尾部插入效率。但是依然無法解決删除效率(删除需要找到前節點).還需要雙向連結清單。前面雖然詳細介紹過雙向連結清單，但是這樣未免太複雜！
是以我們采用帶頭節點的單連結清單在頭部插入删除，把頭部當中棧頂，這樣精了很多。插入直接在頭節點後插入。而删除也直接删除頭節點後第一個元素即可。

結構設計

長話短說，短話不說

。直接上代碼就懂。

連結清單的節點：

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

複制

基本結構：

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

複制

push插入

與單連結清單頭插入一緻，如果不太了解請先看筆者隊線性表介紹的。

和數組形成的棧有個

差別

。就是理論上棧沒有大小限制(不突破記憶體系統限制)。不需要考慮是否越界。

節點 team 入棧
空連結清單入棧 head.next=team;
非空入棧 team.next=head.next;head.next=team;

pop彈出

與單連結清單頭删除一緻，如果不太了解請先看筆者隊線性表介紹的。

和數組同樣需要判斷是否為空。

節點 team 出棧
head指向team後驅節點。 不需要考慮連結清單是否為1個節點 。如果為1個節點，team.next=null.執行完畢head.next=null。變為空，滿足條件。

其他操作

其他例如peek操作時傳回棧頂 不彈出 .是以隻需判空滿足題意時候 return head.next.data 即可。而length你可以周遊連結清單傳回長度，也可以動态設定(本文采取)跟随棧長變化。其他操作直接看api。

實作代碼

數組實作

package 隊棧;

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

複制

連結清單實作

package 隊棧;

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;//頭節點
    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;
    }
       
    }
}

複制

測試

總結

棧的邏輯比較 簡單 。很容易了解，實作起來也相對容易。但是要注意數組情況的界限問題。
後面将介紹隊列 ，相比棧，隊列内容更豐富一些。難度也稍大一些。
如果有 不好需要改進 還請 指出 ！

資料結構與算法—棧詳解(看完面試考試再也不怕了)設計與介紹實作代碼總結

設計與介紹

數組實作

結構設計

push插入

pop彈出并傳回首位

其他操作

連結清單實作

結構設計

push插入

pop彈出

其他操作

實作代碼

數組實作

連結清單實作

測試

總結