# DS Stack

{%hackmd theme-dark %}

## 堆疊

:::info
* LIFO
* 只能從**頂端**取/刪資料
* 只能從**頂端**加資料
:::

## 實作

### Array-based

struct Stack{
    int arr[MAXN], now;
    Stack(): now(0) {}
    int top(){
        return arr[now-1];
    }
    void pop(){
        --now;
    }
    void push(int val){
        arr[now++] = val;
    }
    int size(){
        return now;
    }
};

### Pointer-based

template <typename T>
class Stack {
    struct Node {
        T data;
        Node *next;
        Node(const T &d, Node *n = nullptr) : data(d), next(n) {}
    };
    Node *top;
    int _sz;

   public:
    Stack() : top(nullptr), _sz(0) {}
    bool empty() const { return top == nullptr; }
    void push(const T &d) {
        top = new Node(d, top);
        _sz++;
    }
    T top() {
        return top->data;
    }
    void pop() {
        Node *tmp = top;
        top = top->next;
        delete tmp;
        _sz--;
    }
    int size() { return _sz; }
    ~Stack() {
        while (!empty()) pop();
    }
};

## 例題

### Leetcode - backspace string compare

https://leetcode.com/problems/backspace-string-compare/description/

#### 題目：
模擬鍵盤輸入小寫字母跟backspace，問最後這兩個字串是否一樣

#### 解法：
遇到一般字元就 push，遇到backspace就pop，記得pop前檢查stack是不是空的。

### 括號匹配

#### 題目：
有很多由括號組成的字串問是否合法匹配

#### 解法：
遇到左括號就 push，遇到右括號就 pop，如果 pop 時 stack 是空的(多餘的右括號)或是結束時 stack 不是空的就不合法。

* 這題不用 stack 也能解

### UVA 514

#### 題目：
有一個火車站，出去及進來都只有一條路
有一對列按照編號順序排列的火車
是否能按照給定的順序出車站？

#### 解法：
stack 直接模擬

### 中序轉後序

#### 題目：
給中序式請轉成後序式

#### 解法：
注意運算子的優先順序，數字直接 push，運算子需先將優先度高的算完，再 push 進 stack。

bool InfixToPostfix(List<string> &exp, List<string> &ret) {
        Stack<string> oper;

        // List<string> ret;

        while (!exp.empty()) {
            string cur;
            exp.front(cur), exp.delete_front();
            // cerr << cur << endl;
            if (cur == "(") {
                oper.push(cur);

            } else if (cur == ")") { // -> pop all the operators until "("
                string oper_cur;
                while (!oper.empty()) {
                    oper.gettop(oper_cur);
                    oper.pop();
                    if (oper_cur == "(") break;
                    ret.push_back(oper_cur);
                }
            } else if (isOperator(cur[0])) {
                string _top = "";
                // higher priority operator must be popped(calculated) first
                if (!oper.empty()) oper.gettop(_top);

                while (!oper.empty() && priority(_top[0]) >= priority(cur[0])) {
                    ret.push_back(_top);
                    oper.pop();
                    if (!oper.empty()) oper.gettop(_top);
                }

                oper.push(cur);

            } else if (isOperand(cur)) { // operand can be pushed directly
                ret.push_back(cur);
            }
        }

        string o;
        while (!oper.empty()) { // handle all uncalculated operators
            oper.gettop(o);
            oper.pop();
            if (o != "(") ret.push_back(o);
        }

        return true;
    }

### 運算式結果

#### 題目：
給一運算式求值是多少

#### 解法：
先依上題轉成後序，然後每次算完就放入堆疊，最後答案就是堆疊最頂端(堆疊應只剩一個data)

bool evaluate(List<string> strList, int &ret) {
        ret = 0;
        List<string> tmp = strList;
        Stack<int> s;
        while (!tmp.empty()) {
            string cur;
            tmp.front(cur), tmp.delete_front();
            if (isOperator(cur[0])) {
                int a, b;
                s.gettop(b), s.pop();
                s.gettop(a), s.pop();
                switch (cur[0]) {
                    case '+':

                        s.push(a + b);
                        break;
                    case '-':

                        s.push(a - b);
                        break;
                    case '*':

                        s.push(a * b);
                        break;
                    case '/':
                        if (b == 0) {
                            cout << "### Error: Divided by ZERO! ###\n";
                            return false;
                        }
                        s.push(a / b);
                        break;
                }
            } else {
                int num = atoi(cur.c_str()); // convert string to int
                s.push(num);
            }
        }
        s.top(ret);
        return true;
    }

## 延伸 - 單調堆疊

:::info
維護單調性的堆疊
:::

### 實作

* 如果堆疊為空或比 top 小的進堆疊
* 如果比 top 大就 pop 掉 top

## 例題

### 直方圖最大矩形

[https://leetcode.com/problems/largest-rectangle-in-histogram/](https://leetcode.com/problems/largest-rectangle-in-histogram/)