棧，一種操作受限的線性表焚刚，只允許在一端實(shí)現(xiàn)插入和刪除
注:形狀和操作屈梁，非常類似我們一疊累起來的盤子
1.為什么要使用棧呢嗤练，這種操作受限的線性表榛了，直接使用數(shù)組和鏈表不就行了，操作多而且更靈活潭苞？
答:使用功能上忽冻，確實(shí)能用數(shù)組和鏈表代替棧真朗，但是特定的數(shù)據(jù)結(jié)構(gòu)是對(duì)特定的場(chǎng)景的抽象此疹，而且數(shù)組鏈表暴露了太多操作接口，操作上靈活了遮婶，使用上就不可控蝗碎，自然更容易出錯(cuò)
注:存在有意義，術(shù)業(yè)有專攻旗扑，更加高效低錯(cuò)蹦骑，也說明了棧是繼承抽象的具體使用，數(shù)組和鏈表是抽象
2.使用場(chǎng)景和實(shí)現(xiàn)棧
答:只在某數(shù)據(jù)集合臀防，只在某一端插入刪除數(shù)據(jù)眠菇，且具有后進(jìn)先出(逆序)特性，可用棧實(shí)現(xiàn)袱衷，數(shù)組結(jié)構(gòu)的棧叫順序棧捎废，鏈表結(jié)構(gòu)的棧叫鏈?zhǔn)綏?/p>
3.動(dòng)態(tài)擴(kuò)容的順序棧
答:原理直接來自動(dòng)態(tài)擴(kuò)容數(shù)組，空間不夠時(shí)致燥，申請(qǐng)更大空間登疗，然后copy數(shù)據(jù)過去，由此可知嫌蚤，入棧時(shí)間復(fù)雜度最好o(1)辐益，最差o(n)因?yàn)槭且獢U(kuò)容搬遷，但平均是o(1)脱吱，可用均攤法論證(大多數(shù)情況o(1)極少情況o(n))
注:設(shè)滿棧k智政，申請(qǐng)新空間2k切揭，入棧操作k+k制跟，平攤o(1)
4.棧的操作出棧入棧
只支持入棧出棧操作趟卸，而且可由數(shù)組鏈表實(shí)現(xiàn)训桶，故確實(shí)是一個(gè)操作受限的線性表結(jié)構(gòu)二打，最大特點(diǎn)后進(jìn)先出
注:top指針一直是虛指向语泽，故
arr[top++]=x;
arr[--top]=x;
5.棧的經(jīng)典使用
a.棧在函數(shù)調(diào)用中應(yīng)用
執(zhí)行按照先輸入后執(zhí)行端蛆，先執(zhí)行的函數(shù)只有等到內(nèi)部調(diào)用的其他函數(shù)都執(zhí)行后才能執(zhí)行(jvm內(nèi)存管理中有堆棧概念横媚，方法棧就用來存局部方法和方法中的局部變量)床三，遞歸實(shí)現(xiàn)也是一罩，被調(diào)用函數(shù)的局部變量的作用域也是(局部方法調(diào)用時(shí)，被調(diào)用函數(shù)中變量建立撇簿，被調(diào)用函數(shù)結(jié)束時(shí)聂渊，復(fù)位給調(diào)用函數(shù))差购，遞歸
b.棧在表達(dá)式求值中應(yīng)用
運(yùn)算符有優(yōu)先次序，需要逆序汉嗽，雙棧實(shí)現(xiàn)
入棧規(guī)則:數(shù)據(jù)棧直接入棧欲逃，運(yùn)算棧僅優(yōu)先級(jí)越高才進(jìn)(可保證優(yōu)先輸出)
出棧規(guī)則:僅當(dāng)運(yùn)算棧不能進(jìn)入(運(yùn)算符入棧低于等于棧內(nèi)運(yùn)算符)時(shí)，彈出運(yùn)算棧饼暑，直到能進(jìn)入為止稳析；此時(shí)數(shù)字棧兩個(gè)一彈出，執(zhí)行后數(shù)字存入數(shù)字棧
括號(hào)處理:可以把右括號(hào)看成是優(yōu)先級(jí)最高
c.棧在括號(hào)匹配中應(yīng)用
右左入棧弓叛，右出棧彰居，判空
6.瀏覽器前進(jìn)后退操作實(shí)現(xiàn)原理
你要實(shí)現(xiàn)在一系列進(jìn)棧出棧操作中，一直保存這幾個(gè)頁面撰筷，就需要對(duì)入棧x存陈惰，出棧y存，故需要雙棧實(shí)現(xiàn)毕籽，棧x負(fù)責(zé)后退彈出抬闯，棧y負(fù)責(zé)前進(jìn)彈出
注:
負(fù)責(zé)頁面前進(jìn)操作逆序，退出操作逆序关筒，需雙棧
棧x負(fù)責(zé)用戶查看入棧溶握，退后操作出棧；
棧y負(fù)責(zé)x出棧的數(shù)據(jù)入棧平委，前進(jìn)操作出棧
雙向鏈表也可以實(shí)現(xiàn)同樣功能
