棧：

1.操作：入棧和出棧。
2.先進(jìn)后出。
3.基于數(shù)組實(shí)現(xiàn)：順序棧。
4.基于鏈表實(shí)現(xiàn)：鏈?zhǔn)綏！?

順序棧

// 基于數(shù)組實(shí)現(xiàn)的順序棧
public class ArrayStack {
  private String[] items;  // 數(shù)組
  private int count;       // 棧中元素個(gè)數(shù)
  private int n;           // 棧的大小

  // 初始化數(shù)組，申請(qǐng)一個(gè)大小為 n 的數(shù)組空間
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入棧操作
  public boolean push(String item) {
    // 數(shù)組空間不夠了，直接返回 false，入棧失敗。
    if (count == n) return false;
    // 將 item 放到下標(biāo)為 count 的位置，并且 count 加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出棧操作
  public String pop() {
    // 棧為空，則直接返回 null
    if (count == 0) return null;
    // 返回下標(biāo)為 count-1 的數(shù)組元素，并且棧中元素個(gè)數(shù) count 減一
    String tmp = items[count-1]; //這里只需要一個(gè)額外的空間?？臻g復(fù)雜度為O(1)
    --count;
    return tmp;
  }
}

總結(jié)：?？臻g復(fù)雜度和時(shí)間復(fù)雜度O(1)

棧的應(yīng)用：函數(shù)調(diào)用棧，表達(dá)式求值，括號(hào)匹配，瀏覽器的前進(jìn)后退。
相關(guān)code:https://github.com/wangzheng0822/algo/tree/master/java/08_stack