Stack (堆疊)

假設你有一些書把他們疊起來，一層一層的往上疊，所以每次新的書本會放在最上面，而當想要拿取書本的時候，也是從最上面的開始拿。當然現實生活會有可能從中間抽出書本，不過在程式中是不可以的，在程式世界下圖會更貼切。

所以這是一種資料結構，後進先出(Last-In-First-Out, LIFO)

河內塔故事中的每一個柱子都是Stack結構

柱子最上方的盤子，一定是最先被拿起來的

平常生活有時候也會發生 Stack 的情境，人會最優先處理最後發生的事

做事做到一半時，突然一件更緊急的事發生

這時就會先把打斷的事做完，才回來繼續做原來的事

Stack 支援那些操作呢

Push x - 把 x 塞到Stack的上面
Pop - 把 Stack 最上面的元素抽離
Top - 看看 Stack 最上面的元素是什麼
Clear - 把 Stack 清空

玩玩看 : https://www.cs.usfca.edu/~galles/visualization/StackArray.html

範例 - 自製Stack

[操作說明]

push x : 放入整數 x 進入stack

pop : 將stack中的整數拿出來

[input]

push 9
push 5
push 2
push 7
pop
pop
pop
push 1
pop
pop
pop

[output]

 pop: 7
 pop: 2
 pop: 5
 pop: 1
 pop: 9
 pop: nothing in stack

[說明]

讓 stack_top 永遠等於最後一個元素的位置+1
一開始 stack 中沒有任何元素，令 stack_top = 0
當 stack 中沒有元素時就不能 pop

[Code]

#include<bits/stdc++.h>
using namespace std;

int stk[105], stack_top;


int main ()
{
    string cmd;
    int i;

    stack_top = 0;

    while( cin >> cmd ){
        if( cmd == "push" ){
            cin >> i;
            stk[stack_top] = i;
            stack_top++;
        }
        else if( cmd == "pop" ){
            if( stack_top == 0 )
                cout << " pop: nothing in stack" << endl;
            else{
                cout << " pop: " << stk[stack_top-1] << endl;
                stack_top--;
            }
        }
    }

    return 0;
}

[題目練習]

b923: stack 堆疊的模板題

https://zerojudge.tw/ShowProblem?problemid=b923

B304: Parentheses Balance

https://zerojudge.tw/ShowProblem?problemid=b304

解題要點：

一個字串變數負責存括號們
一個stack去把左括號存起來
碰到右括號的時候把stack的資料pop出來比對是否成對，沒成對代表"資料格式不對"
最後要取清算stack是否為空，沒空的話代表"資料格式不對"

解答：

#include<bits/stdc++.h>
#include <stack>
using namespace std;

int main(void){

    int n;
    string str;
    stack<int> stk;

    cin>>n;

    for(int i = 0 ;i<n;i++){

        cin>>str;
        bool pass = true;

        for(int j = 0 ;j<str.length();j++){

            if(str[j]=='('||str[j]=='['){
                stk.push( str[j] );
            }
            else if(stk.empty()){
                pass=false;
                break;
            }
            else if(str[j]==')'){
                if(stk.top()!='('){
                    pass=false;
                    break;
                }
                stk.pop();
            }
            else if(str[j]==']'){
                if(stk.top()!='['){
                    pass=false;
                    break;
                }
                stk.pop();
            }
        }

        if(!stk.empty()){
            pass = false;
        }

        if(pass==true)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;

    }

}

d016: 後序運算法

http://zerojudge.tw/ShowProblem?problemid=d016

輸入一個字串，並且取得長度與資料

#include <iostream>
#include <stack>
#include <sstream>

using namespace std;

int main(int argc, char *argv[]){
    string ins;
    int op1, op2, ans, i, j, k;
    stringstream ss;

    while(getline(cin, ins)){
        i = j = k = 0;
        stack<int>myStack;
        while(i<ins.length()){
            if(ins[i] >= '0' && ins[i] <= '9'){                   // 數字
                for(j=i+1; j<ins.length(); j++)               //找出所在區段
                    if(ins[j] == ' ')
                        break;
                string tmp = ins.substr(i, j-i);             //用substr抓出數字
                ss.str("");
                ss.clear();                                      //google到的結果說要這樣清空
                ss << tmp;
                ss >> op1;
                myStack.push(op1);
                i = j;
                i++;
            }
            else if(ins[i] == '+'){
                op2 = myStack.top();
                myStack.pop();
                op1 = myStack.top();
                myStack.pop();
                myStack.push(op1+op2);
                i+=2;
            }
            else if(ins[i] == '-'){
                op2 = myStack.top();
                myStack.pop();
                op1 = myStack.top();
                myStack.pop();
                myStack.push(op1-op2);
                i+=2;
            }
            else if(ins[i] == '*'){
                op2 = myStack.top();
                myStack.pop();
                op1 = myStack.top();
                myStack.pop();
                myStack.push(op1*op2);
                i+=2;
            }
            else if(ins[i] == '/'){
                op2 = myStack.top();
                myStack.pop();
                op1 = myStack.top();
                myStack.pop();
                myStack.push(op1/op2);
                i+=2;
            }
            else if(ins[i] == '%'){
                op2 = myStack.top();
                myStack.pop();
                op1 = myStack.top();
                myStack.pop();
                myStack.push(op1%op2);
                i+=2;
            }
        }
        cout<<myStack.top()<<endl;
    }

    return 0;
}

3-3 Stack