第四章 棧與隊(duì)列

棧：限定僅在表尾進(jìn)行插入和刪除操作的線性表。（后進(jìn)先出的線性表），簡稱LIFO結(jié)構(gòu)。

允許插入和刪除的一端為棧頂，相對的則為棧底。

棧結(jié)構(gòu).png

tips：

1.棧滿（top1 + 1 == top2）
2.鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
3.遞歸函數(shù)：一個(gè)直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)。

隊(duì)列：只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。（先進(jìn)先出的線性表），簡稱FIFO結(jié)構(gòu)。

允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。

隊(duì)列結(jié)構(gòu).png

tips：

1.循環(huán)隊(duì)列：隊(duì)列的頭尾相接的順序存儲(chǔ)結(jié)構(gòu)。
2.隊(duì)列滿的判斷方法：
（1）設(shè)置標(biāo)志變量
（2）隊(duì)列空為front == rear，隊(duì)列滿為（rear+1）% QueueSize == front。此時(shí)隊(duì)列長度為（rear-front+QueueSize）%QueueSize
3.隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：尾進(jìn)頭出的線性表的單鏈表，簡稱為鏈隊(duì)列。
4.在已知隊(duì)列長度最大值的情況下選擇循環(huán)隊(duì)列，否則選鏈隊(duì)列。