隊列與棧的原理及特點（概括屉更，詳解在下面）
棧 Stack
1.先進后出
2.入棧（進棧）push
3.出棧（彈出）pop
4.棧的本質(zhì)是一個特殊的線性數(shù)組（表）晓褪。特殊在只能在表尾進行插入和刪除操作。
5.有順序棧和鏈棧兩種（這里自己去了解一下吧）
隊列 queue
1.先進先出
2.表尾插入，表頭刪除
3.隊列也是一種線性表
4.順序隊列和鏈對芳誓，以循環(huán)順序隊列更加常見
正題前的一個問題（答案在下文）
棧的淺談
&emsp啊鸭；棧提供push和pop接口锹淌，所以棧不提供迭代器（iterator），及不能遍歷它赠制。所以STL中棧往往不被歸為容器赂摆，而被歸類為容器適配器container adaapter钟些。
&emsp；那就帶來一個問題政恍，STL中棧用什么實現(xiàn)呢？ 上圖
可以看到椄莺模可以用數(shù)組或者鏈表來實現(xiàn)迫筑，vector，deque宗弯，list。
用棧實現(xiàn)隊列
push（x）----將一個元素放入隊列的尾部
pop（）----- 從隊列首部溢出元素
peek（）----- 返回隊列首部的元素
empty（） ----- 返回隊列是否為空
注意
&emsp辕棚；在push數(shù)據(jù)的時候，只要數(shù)據(jù)放進輸入棧就好邓厕，但在pop的時候逝嚎，操作就復雜一些，輸出棧如果為空邑狸，就把進棧數(shù)據(jù)全部導入進來（注意是全部導入）懈糯，再從出棧彈出數(shù)據(jù)单雾，如果輸出棧不為空，則直接從出棧彈出數(shù)據(jù)就可以了硅堆。
&emsp；如果進棧和出棧都為空的話够掠，說明模擬的隊列為空了。
正題
&emsp疯潭；拿一道題來說吧。匹配括號竖哩，及字符串要有" ( " , " ) " , " [ " , " ] " , " { " , " } " 成對出現(xiàn)脊僚。常見于我們敲代碼括號要匹配。
&emsp辽幌；三種情況：
1.第一種，字符串左方向括號多余不匹配乌企。
2.第二種，括號沒有多余逛犹，但類型不對。
3.第三種舞蔽，字符串右方向括號多余不匹配码撰。
&emsp渗柿；而我們需要的是運用棧的先進后出脖岛，或者叫后進的先出，依次遍歷數(shù)組字符串柴梆，讀到的左括號放進棧中，遇到匹配就出棧绍在，此時就會有三種情況雹有。
1.已經(jīng)遍歷完了字符串臼寄，但是棧不為空，說明有相應(yīng)的左括號沒有右括號來匹配吉拳，所以return false。
2.遍歷字符串匹配的過程中煤惩，發(fā)現(xiàn)棧里沒有要匹配的字符。所以return false盟庞。
3.遍歷字符串匹配的過程中汤善，棧已經(jīng)為空了，沒有匹配的字符了红淡，說明右括號沒有找到對應(yīng)的左括號return false。
當遍歷完在旱，棧時空的，那說明完全匹配驻仅。
bool IsValid(string s)
{
stack<int> st;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '(')
st.push(')');
else if (s[i] == '{')
st.push('}');
else if (s[i] == '[')
st.push(']');
else if (st.empty() || st.top() != s[i])
return false;
else
st.pop(); // st.top() == s[i]
}
return st.empty();
}
*這里其實遞歸就是使用了棧登渣，每一次遞歸調(diào)用都會把函數(shù)的局部變量、參數(shù)值和返回地址等壓入調(diào)用棧中胜茧，然后遞歸返回的時候，從棧頂彈出上一次遞歸的各項參數(shù)呻顽，所以這就是遞歸為什么可以返回上一層位置的原因*
由于參數(shù)多，全局變量等等嬉愧，使用遞歸很容易判斷不充分return的條件喉前，非常容易無限遞歸（或者遞歸層級過深）没酣，造成棧溢出錯誤
文章參考（如有侵權(quán)聯(lián)系刪除）：https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484531&idx=1&sn=448cab9a64c6cd00ed55dee847db0c4c&chksm=f9a23722ced5be34488fde245f09dd613d5a45ea9b036615f285b76d4b95b15ff46bb720ad09&scene=178&cur_album_id=1577943906476998657#rd
