一娶吞、棧
棧（stack）是限定僅在表尾（棧頂）進(jìn)行插入和刪除操作的線(xiàn)性表垒迂。
后進(jìn)先出(LIFO)：
棧的順序儲(chǔ)存結(jié)構(gòu)（數(shù)組）
兩棧共享空間
關(guān)鍵思路：它們是數(shù)組兩端妒蛇，向中間靠攏机断。top1和top2分別是棧1和棧2的棧頂指針楷拳。
棧1為空，top1 = -1,;棧2為空吏奸，top2 = n;
判斷棧滿(mǎn)欢揖，top1+1 == top2
棧的鏈?zhǔn)絻?chǔ)存：鏈棧
棧頂指針在頭部，單鏈表中的比較常用的頭結(jié)點(diǎn)失去意義奋蔚，通常鏈棧無(wú)需頭節(jié)點(diǎn)她混。
//單鏈表基礎(chǔ)結(jié)構(gòu)
template<class DataType>
struct Node{
DataType data;
Node<DataType> *next;
};
//使用時(shí)需多聲明一個(gè)棧頂指針top
Node<DataType> *top = new Node<DataType>;
棧的應(yīng)用——遞歸
斐波那鍥數(shù)列：前面相鄰兩項(xiàng)之和，構(gòu)成后一項(xiàng)泊碑。
- 遞歸：函數(shù)直接或間接調(diào)用自身（反復(fù)調(diào)用坤按，建立大量函數(shù)副本；但結(jié)構(gòu)清晰馒过、簡(jiǎn)潔）臭脓。
- 迭代：無(wú)需反復(fù)調(diào)用和占用額外內(nèi)存。
棧的應(yīng)用——四則運(yùn)算表達(dá)式求值
后綴（逆波蘭）表示法：
-
將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式（棧用來(lái)進(jìn)出運(yùn)算的符號(hào)）沉桌；
-
將后綴表達(dá)式進(jìn)行運(yùn)算得出結(jié)果（棧用來(lái)進(jìn)出運(yùn)算的數(shù)字）
二谢鹊、隊(duì)列（queue）
隊(duì)列：先進(jìn)先出（FIFO）
- 入隊(duì)（插入）：新元素始終添加在隊(duì)列的末尾；
- 出隊(duì)（刪除）：發(fā)生在隊(duì)頭留凭，只能移除第一個(gè)元素；
應(yīng)用非常頻繁：鍵盤(pán)輸入“god”,若使用棧偎巢，輸出“dog”;使用隊(duì)列蔼夜，輸出“god”
為避免隊(duì)頭、隊(duì)尾處理麻煩：front指針指向隊(duì)頭元素压昼，rear指針指向超尾元素求冷。
存在問(wèn)題：“假溢出”現(xiàn)場(chǎng)窍霞，隊(duì)尾滿(mǎn)了匠题，但隊(duì)頭還是空閑。
循環(huán)隊(duì)列：頭尾相接的順序儲(chǔ)存結(jié)構(gòu)韭山。
存在問(wèn)題：當(dāng)
front與rear指針重合時(shí)，隊(duì)列存在空或滿(mǎn)兩種情況冷溃。
解決方法：
- 設(shè)標(biāo)志變量
flag钱磅，當(dāng)front==rear,flag=0,隊(duì)列為空；當(dāng)front==rear,flag=1,隊(duì)列滿(mǎn)似枕，- 隊(duì)列空時(shí)盖淡，
front==rear；隊(duì)列滿(mǎn)時(shí)凿歼，保留一個(gè)元素空間褪迟。
★:-隊(duì)列滿(mǎn)的條件是(rear+1)%QueueSize == front冗恨；
★:-通用計(jì)算隊(duì)列長(zhǎng)度公式:(rear - front + QueueSize)%QueueSize
☆:-采用%QueueSize防止長(zhǎng)度溢出——最多一整圈。
鏈隊(duì)列：只能尾進(jìn)頭出的線(xiàn)性表的單鏈表味赃。
若可以確定隊(duì)列長(zhǎng)度最大值，建議用循環(huán)隊(duì)列 洁桌；無(wú)法預(yù)估隊(duì)列長(zhǎng)度渴丸，則使用鏈隊(duì)列。
