棧

定義：

1.棧（stack）是一種特殊的線性資料結構，棧中的元素是按照入棧順序線性的排列。

2.棧的結構如下圖所示，僅允許在表的一端進行插入和刪除運算，這一端被稱為棧頂，相對地，把另一端稱為棧底。

3.棧的特點是後進先出（LIFO，Last In First Out），即最後入棧的元素最先出棧。

棧的實現：

陣列模擬（手工棧）：

STL棧：

棧的應用：

　　接下來有的小盆友可能會問：「這玩意有啥用？沒陣列簡便，執行還賊慢！」

　　其實在遞迴函數中，就是不斷壓棧彈棧的一個過程。

初識應用：

例題：

http://ybt.ssoier.cn:8088/problem_show.php?pid=1353

1353：表示式括號匹配(stack)

時間限制: 1000 ms 記憶體限制: 65536 KB
提交數: 23740 通過數: 12484

【題目描述】

　　假設一個表示式有英文字母（小寫）、運運算元（ $+ ， — ， * ， /$

【輸入】

一行資料，即表示式。

【輸出】

一行，即「 $Y E S$

【輸入樣例】

2*(x+y)/(1-x)@

【輸出樣例】

YES

【提示】

【樣例輸入2】

(25+x)*(a*(a+b+b)@

【樣例輸出2】

NO

【程式碼】

這程式碼乍一看沒什麼問題，但是…………

又去洛古提交了顯示「RE」，說明爆棧，但是這個棧怎麼變大？？？？？？？？？？？？？？？

於是換了種思路：

兩邊都AC了！！！

程式碼：

思路都差不多

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int top=0;
    getline(cin,s);
    for(int i=0;i<s.size()-1;i++){
        if(s[i]=='(') top++;
        else if(s[i]==')') top--;
        if(top<0) break;
    }
    if(top!=0) cout<<"NO";
    else cout<<"YES";
    return 0;
}

棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧