Stack

• What is Stack
  1.有top與bottom
  2.First In Last Out

• Stack Representation
  1.Push(Add)
  2.Pop(Delete)

• ADT(Abstract Data Type)
  把一個data structure抽象化
  1.Data stored：有什麼成員、要存什麼資料在裡面
  2.operation：可以做什麼操作
  3.error condition：什麼時候會有error，定義清楚

• ADT of Stack
  1.data stored：隨意的物件
  2.operation：push()、pop()、top()、size、empty()
  3.error：例，若pop時，stack內沒有東西

• C++ Run Time Stack
  若是在C++內呼叫函式，則會先把原先的函式存下pc、變數值並push進Stack中。

• Paraentheses Matching
  若是左括弧則push，又括弧則pop出左括弧

• Infix --> Postfix
  1.好處：
  a.不用用括號
  b.不用考慮先乘除後加減
  **2.如何做：
  三步驟
  a.先加上所有括號

    ex : a / b - c + d \* e - a \* c --> \(\(\(\(a / b\) - c\) + \(d \* e\)\) - \(a \* c\)\)  
  

  b.把每個operator置換掉對應的右括弧
  c.刪除所有括號 3.規則：
  a.沒括號

    看到變數直接output  
    看到operator便放進stack中  
    檢查stack中的operator，若放進去之operator壓不住（優先順序一樣也算壓不住）stack的operator，則先pop出優先順序  
    大於要放入operator的元素，直到要放入的operator大於stack->top，再push進stack  
    若最後沒有變數了，再把剩餘的stack中元素依序pop出  
  

  b.有括弧

    若遇到左括弧，直接push進stack  
    若遇到右括弧，將stack中的元素pop出，直到碰到左括弧**
  

• 運算Postfix
  1.只需由左至右掃一遍-->O(n)
  2.把變數放入stack，碰到operator則抓出k個（看此運算需要幾個）做運算，做完再塞回stack