⑴ 數據結構——知識點總結-棧和隊列
數據結構：棧與隊列的深度解析
棧，這個術語源自拉丁文"staurus"，意為"矛尖"，形象地描繪了其像矛尖一樣只允許在一端進出的特點。它是線性數據結構的一種，遵循FILO（First In Last Out，先進後出）原則，如同子彈出膛的順序。主要有順序棧和鏈棧兩種實現方式。
與之相對的是隊列，它遵循的是FIFO（First In First Out，先進先出）策略，像食堂排隊打飯一樣，遵循先到先服務。隊列同樣有兩種基礎形式，即順序隊列和鏈隊。
理解它們的操作至關重要，包括初始化、基本的入棧與出棧操作，以及滿/空狀態的判斷。棧在括弧匹配、中綴/前綴/後綴表達式轉換中大顯身手，而隊列則在共享棧和雙端隊列的習題中體現其靈活性。
實戰挑戰
- 體驗後進先出的棧操作，如快速解決問題：後進先出。
- 掌握棧與隊列的邊界管理：實現滿、空狀態的檢測。
- 理解n-i+1的巧妙應用：隊列的動態操作。
- 探索未知的可能：在特定情境下，探索不同數據結構的性能差異。
- 在C語言中實踐：運用棧實現遞歸調用和表達式求值。
- 棧的多元素操作：連續push和pop操作。
- 挑戰隊列的邊界操作：更新top元素和調整指針。
- 隊列的特殊情況：隊尾元素可能需要更新頭尾指針。
- 深入理解遞歸調用：如何用棧來支持遞歸過程。
- 循環隊列的入隊魔術：rear位置更新的技巧。
- 隊列狀態變化後的觀察：front和rear的新位置。
- 判斷隊列是否為空：通過比較front和rear。
- 共享特性：棧與隊列都遵循端點操作原則。
習題詳解
- 入隊序列{a,b,c,d,e}可能的出隊序列：D. {e,c,b,a,d}，因為隊列遵循先進先出。
- 棧的出棧序列：入棧為{a,b,c,d,e}，可能的出棧序列包括d,e,c,b,a等，但不包括C選項中的順序。
- 循環隊列初始化：front=0, rear=n-1，確保隊列有足夠空間。
- 中綴表達式到後綴表達式的轉換：當有5個操作符時，可能需要轉換為後綴表達式。
- 棧的元素轉換：入棧n個元素，出棧為3，最多可能有n-1個元素。
棧和隊列，這兩個看似簡單的數據結構，卻蘊含著無限的奧秘和應用場景。熟練掌握它們，是數據結構學習旅程中的重要一步。