一.什么是棧

堆棧又名棧（stack），它是一種運算受限的數據結構（線性表），只不過他和數組不同，數組我們可以想象成一個裝巧克力的盒子，你想拿一塊巧克力，不需要改變其他巧克力的位置，而棧就相當于是一個只有上方有一個口且寬度只能容納一塊巧克力的盒子，如圖：

那如果我們想拿最下面的巧克力該怎么辦呢？就需要把這顆巧克力上面的所有巧克力都取出，這樣才能取出最下面的巧克力。我們可以把棧想象成是一個封了底的數組，要想拿走一個值就需要把它上面的所有值都取出，同理，如果我們想加入一個數據，也只能加到棧的最頂端。這就是棧。

二.棧的具體實現?

1.手寫棧

如果要手寫一個棧，我們優先選擇用和棧差別最小的數組模擬棧，我們要想模擬一個棧，需要擁有幾個操作函數，如下。

①我們要編寫push函數，作用是往棧里輸入數據

? ? ?要想編寫這樣一個函數，我們首先需要確定數組（棧）的頂端，再把數放進去。我們可以定義一個棧的長度變量，初始值為0，你每輸入一個數據就++。這樣就可以很好的解決棧的輸入了，我們看代碼：

void push(char x) {  //top是棧的長度，M是所模擬的數組的長度，s是棧的名字，x是要往棧頂放的數if(top<M) {    //判斷棧的長度不超過模擬它的數組的長度，則可以輸入。top++;     //將棧頂++s[top]=x;  //把棧頂值設為x}
}

②我們要編寫GetTop 函數，作用是獲取棧頂的值

? ? ? 這個很簡單，我們直接獲取數組的第top項就可以了。我們看代碼：

char getTop() {return s[top];  //返回棧頂元素
}

③我們要編寫彈棧函數，目的是刪除棧頂元素，以取出下一個元素。

? ? ?我們可以直接讓top--，這樣原來的棧頂元素就不在這個棧中了，也就刪除了棧頂元素。我們看代碼:

void pop() {if(top>0) {  //如果棧不空top--;   //刪除棧頂元素}
}

④我們要編寫Getlen函數，目的是獲取棧的長度。

? ? ? ?由于top就是代表著棧頂元素的位置，所以我們只要返回top的值就可以了。我們看代碼：

int getlen() {return top;
}

接下來把所有函數都放在一起發個程序：

#include<iostream>
using namespace std;
const int M=10;   //M大小可動態調整
int s[M+1];
int top=0;
void push(int x) {if(top<M) {top++;s[top]=x;}
}
void pop() {if(top>0) {top--;} 
}
int getTop() {return s[top]; 
}
int getlen() {return top;
}int main() {return 0;
}

二.STL模板

有的人可能會說，手寫棧實在太麻煩了，有沒有簡單的方法呢？當然有！接下來我就給大家講。

STL模板不需要你手動定義棧中的函數，他已經給你定義好了函數和對應的棧，也不用你再用數組模擬了。但想用這個定義好了的棧，我們要導入一個頭文件，如下

#include<stack>

一切準備就緒，我們要想定義一個STL棧，需要用如下代碼：

stack<int>s; 

就是stack后面尖括號里寫數據類型，然后再寫一個棧名就可以了。

STL棧里面有一些常用的函數。

1.push，作用是往棧里輸入一個數據，只不過是用棧名.push(輸入的數據）的方式輸入。如下：

s.push(x)

?2.top，和上面的Gettop函數的作用相同。也需要用棧名.top()的方式來調用。如下：

s.top();

3.pop，和上面的pop作用相同。如下：

s.pop();

4.size，和上面的Getlen函數作用相同。如下：

s.size();

三.例題

題目描述

假設一個表達式有英文字母（小寫）、運算符（+、-、*、/）和左右小（圓）括號構成，以?@?作為表達式的結束符。請編寫一個程序檢查表達式中的左右圓括號是否匹配，若匹配，則輸出?YES；否則輸出?NO。表達式長度小于?255，左圓括號少于?20?個。

輸入格式

一行：表達式。

輸出格式

一行：YES?或?NO。

輸入輸出樣例

輸入 #1復制

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

輸出 #1復制

YES

輸入 #2復制

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

輸出 #2復制

NO

說明/提示

表達式長度小于?255，左圓括號少于?20?個。

?程序?(裝逼代碼）：

#include<bits/stdc++.h>
using namespace std;
stack<char> a;
int main() {string s;cin>>s;for(int i=0; i<s.length(); i++) {if(s[i]=='(') {a.push(s[i]);}if(s[i]==')') {if(a.size()>=1&&a.top()=='(') {a.pop();} else {cout<<"NO";return 0;}}}if(a.size==0)cout<<"YES";else cout<<"NO";return 0;
}