棧和隊(duì)列
棧是一種先進(jìn)后出 只能在表尾進(jìn)行插入和刪除的線性表灵嫌，我們把允許插入和刪除的一端叫做棧頂壹罚，另一端叫做棧底。不含任何數(shù)據(jù)元素的叫做空棧寿羞。LIFO結(jié)構(gòu)猖凛。
棧不一定是順序存儲(chǔ)結(jié)構(gòu)的線性表，棧也可能是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表绪穆，簡稱鏈棧辨泳。
1.2.3 入棧順序，出棧的順序一定是3玖院，2菠红，1嗎？ 很顯然不是难菌。因?yàn)闂Ｖ粚Τ鰲：腿霔５奈恢镁托辛思s束试溯，即表尾(棧頂)但是并沒有對出棧和入棧的時(shí)間進(jìn)行約束。
棧由于是一種特殊的線性表郊酒，它也分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)遇绞。
- 順序棧。類比數(shù)組燎窘，數(shù)組的尾巴模擬棧頂
- 鏈棧摹闽。 去掉頭結(jié)點(diǎn)，雖然頭結(jié)點(diǎn)不是必須的褐健，但是常規(guī)都有付鹿，頭指針和棧頂指針合二為一。這樣的話，原來判斷空棧的條件是頭指針的執(zhí)行為NULL倘屹。變?yōu)闂ｍ斨羔榯op = NULL
` 入棧 s = (Node*)malloc(sizeof(Node)); s->next = S->top; S->top = s; S->count ++; return OK`
` 出棧 p = S->top; S->top = p->next ; free(q);S->Count -- ; `
共享?xiàng)?/p>
兩個(gè)相同類型的棧银亲，通過橫過來，讓一個(gè)的棧底變?yōu)閿?shù)組下標(biāo)的0處纽匙，另外一個(gè)變?yōu)閿?shù)組下標(biāo)的末端即n-1處务蝠。這樣如果兩個(gè)棧增加元素，就是兩端點(diǎn)向中心延伸烛缔。
棧的一個(gè)主要應(yīng)用：遞歸
菲波那切數(shù)列
func Fbi(number:Int)->Int{ if number<2{ return number == 0 ? 0 : 1 return Fbi(number- 1) + Fbi(number -2 ) } }
逆波蘭表示
后綴表達(dá)式的用法馏段，遇到數(shù)字就入棧，遇到運(yùn)算符就出棧践瓷，進(jìn)行運(yùn)算院喜。
隊(duì)列
隊(duì)列是一種特殊的線性表。
鏈隊(duì)列插入元素s
s->next = NULL
Q->rear->next = s
Q->rear = s
