棧與隊列

? 申明：由于篇幅限制，文章可能有些簡略，如果大家想要詳細了解，請一定要百度一下，并閱讀例題，完成習題

緒言：計算機科學在過去的數十年內發展飛速，各種新穎的技術紛至沓來：5G，VR，AI；大數據，可視化，區塊鏈；品種多樣，令人目不暇接。可是在這繁多的技術與科技背后，卻隱藏這這樣一個亙古不變的公式。

算法 ?+? 數據結構 ?=? 大千世界

? ? 算法的定義：解題方案的準確而完整的描述，是一系列解決問題的清晰指令。

? ? 數據結構的定義：計算機存儲、組織數據的方式。

? ? 今天，讓我們從最基礎的數據結構——棧(Stack)和隊列(Queue)開始，透過大千世界的幻影探索它的真實。

?????棧和隊列可以說是每一本的數據結構書都會加以介紹的最基本的數據結構，也是為數不多的線性數據結構。它們是所有數據結構初學者所必須掌握的知識。

?????棧在百度百科上的定義：又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。如圖

????隊列在百度百科上的定義：和棧一樣，隊列是一種操作受限制的線性表，不同之處在于它只允許在表頭進行刪除操作，在表尾進行插入操作。如圖。

????由于都是受限制的線性表，所以在定義這兩種數據結構的時候都只需要一個線性表A?，但在這兩種數據由于操作不同，我們也需要兩組不同的指針加以甄別。如圖所示：

????棧和隊列的操作很簡單，棧只有在表尾進行插入和刪除操作，也就是入棧和出棧；而隊列也僅有在表尾進行插入和表頭進行刪除，也就是入隊和出隊操作。如圖：

????上訴代碼實現了一個基本的棧和隊列的功能，有興趣的同學可以把這段代碼copy后運行，自己編制幾組數據進行檢驗，如果能夠用草稿紙模擬一下過程是再好不過。

????只不過，唯一有一些可惜的是上述代碼中隊列的實現似乎有一些浪費額外空間，這是由于隊列進行出隊操作后，隊首指針之前的數據沒有了再使用的可能性，卻依然占用空間導致，這種隊列稱為順序隊列。

????解決方法有兩種，一種是使用鏈表來實現隊列，在隊首元素出隊后，直接釋放指針空間，這種隊列稱為鏈式隊列；另一種方法就是使用循環隊列。如圖：

????循環隊列的核心是：在一定寬度范圍內，保證每一個隊內的元素反復使用寬度內的空間。實現的方式就是模運算一旦隊尾或者隊首超過寬度限制，通過取余運算使之返回限定的寬度的頭部。

????這樣，通過模運算，使得整個序列的寬度限制在lim內。值的一提的是，這時已經不能用p>q來表示隊列已空，因為隊列循環的情況下p>q是合法的。

????通過以上的描述，大家可能對棧和隊列的基本知識有一定的了解，現在給出兩道例題，嘗試用這兩種數據結構去解決一些實際問題。

????上述兩道題詳細的向我們描述了應該如何用棧和隊列這種數據結構去解題。請詳細揣摩，如果能夠代碼實現，一定會有很大的收獲。

????從此，通過棧和隊列中兩種里程碑式的數據結構，我們進入了它的大門，而這也是我們學習它的開始。

????下面給出一些練習題，如果有興趣，大家可以去嘗試一二。

T1：https://www.luogu.com.cn/problem/P1044 ?棧的基礎知識理解。

T2：https://www.luogu.com.cn/problem/UVA12265 類似例題1

T3：https://www.luogu.com.cn/problem/P1823 二分+棧

T4：https://www.luogu.com.cn/problem/P1886 例題2模板題

謝謝閱讀。

寫留言