一、棧 （Stack）
定義：棧是限定在表尾進(jìn)行插入和刪除操作的線性表幕随。
- 棧的插入操作蚁滋，叫作進(jìn)棧，也叫壓棧赘淮、入棧枢赔。
- 棧的刪除操作，叫作出棧拥知，也叫彈棧踏拜。
- 后出先進(jìn)的方式處理集合
1.常用API：
- Count : 返回元素個(gè)數(shù)；
- Push() : 入棧的方法低剔；
- Pop() : 出棧的方法速梗，并在該隊(duì)列中刪除該元素肮塞；
如果在調(diào)用Dequeue()方法時(shí)，隊(duì)列中沒有元素姻锁，就會(huì)拋出異常 - Peek() : 讀取一個(gè)元素枕赵，但不刪除它。
2.棧的應(yīng)用——遞歸
- 斐波那契數(shù)列——兔子繁殖問題
數(shù)學(xué)函數(shù)定義：
- 遞歸定義——把一個(gè)直接調(diào)用自己或通過(guò)一系列調(diào)用語(yǔ)句間接調(diào)用自己的函數(shù)位隶，稱作遞歸函數(shù)拷窜。
3.棧的應(yīng)用——四則運(yùn)算表達(dá)式求值
-
后綴（逆波蘭）表示法定義——一種不需要括號(hào)的后綴表達(dá)法
例：9+(3-1)×3+10÷2，后綴表達(dá)：9 3 1 - 3 * + 10 2 / +
(1) 初始化一個(gè)空棧涧黄；
(2) 后綴表達(dá)式篮昧，前三個(gè)都是數(shù)字，9笋妥、3懊昨、1進(jìn)棧；
(3) 第四個(gè)是 - 春宣，1作為減數(shù)酵颁，3作為被減數(shù)，運(yùn)算3-1 = 2 月帝，將2進(jìn)棧躏惋；
(4) 接著是數(shù)字 3 進(jìn)棧；
(5) 后面是 * 嚷辅，意味著3其掂，2出棧并相乘，得到6進(jìn)棧潦蝇；
(6) 接著是 + 款熬，6、9出棧相加攘乒，得到15贤牛，15進(jìn)棧；
(7) 接著是10则酝、2進(jìn)棧殉簸；
(8) 后面是 / ，10沽讹、2出棧相除般卑，得到5并進(jìn)棧；
(9)最后是 + 爽雄，15蝠检，5出棧相加，得到20挚瘟；
-
中綴表達(dá)式轉(zhuǎn)后綴——標(biāo)準(zhǔn)的四則運(yùn)算表達(dá)式即為中綴表達(dá)式
例如：9+(3-1)×3+10÷2轉(zhuǎn)化為后綴表達(dá)式 9 3 1 - 3 * + 10 2 / +
(1) 初始化一個(gè)空棧叹谁；
(2) 第一個(gè)字符是9饲梭，輸出9，后面是符號(hào) +焰檩，進(jìn)棧憔涉；
(3) 第三個(gè)是（ ，是左括號(hào)析苫，未配對(duì)兜叨，進(jìn)棧；
(4) 第四個(gè)字符是 3衩侥，輸出国旷，總表達(dá)式為9 3，接著是 -顿乒，進(jìn)棧议街；
(5) 接下來(lái)是 1泽谨，輸出璧榄，總表達(dá)式為9 3 1 ，后面符號(hào)是 ）吧雹。此時(shí)需要去匹配此前的 （ 骨杂，所以棧頂依次出棧，并輸出雄卷，直到（ 出棧為止搓蚪；輸出表達(dá)式為 9 3 1 - ；
(6) 接著是數(shù)字3丁鹉，輸出妒潭，總表達(dá)式為9 3 1 - 3；緊接著是 × 揣钦，因?yàn)榇藭r(shí)棧頂符號(hào)為 + 雳灾，優(yōu)先級(jí)低于 ×，所以不輸出冯凹；*進(jìn)棧谎亩；
(7) 之后是符號(hào) +，此時(shí)當(dāng)前棧頂元素 * 比這個(gè) + 的優(yōu)先級(jí)高宇姚，因此棧中元素出棧并輸出匈庭，總表達(dá)式為 9 3 1 - 3 * + 。然后將當(dāng)符號(hào) + 進(jìn)棧浑劳，
二阱持、隊(duì)列 （Queue）
定義：只允許在一段進(jìn)行插入操作，另一端進(jìn)行刪除操作的線性表魔熏。
- 隊(duì)列是一種先進(jìn)先出的線性表紊选。
- 允許插入的一端叫做隊(duì)尾啼止，允許刪除的一端叫做隊(duì)頭。
1.常用API
- Count : 返回隊(duì)列中的元素個(gè)數(shù)兵罢；
- Enqueue() : 在隊(duì)列的尾端添加一個(gè)元素献烦；
- Dequeue() : 在隊(duì)列的頭部添加一個(gè)元素，并在該隊(duì)列中刪除該元素卖词；
如果在調(diào)用Dequeue()方法時(shí)巩那，隊(duì)列中沒有元素，就會(huì)拋出一個(gè)異常此蜈； - Peek() : 在隊(duì)列頭部讀取一個(gè)元素即横，但不刪除它。
2.循環(huán)隊(duì)列
- 隊(duì)列順序存儲(chǔ)結(jié)構(gòu)裆赵。
- 循環(huán)隊(duì)列定義——把隊(duì)列頭尾相接的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列东囚。
