1、棧

1.1?棧的定義

棧是只能通過訪問它的一端來實現數據的存儲和檢索的一種特殊的線性數據結構。棧的修改要遵循先進后出的原則，這個是棧的核心。在棧中進行插入和刪除操作的一端稱為棧頂（Top）。另一端被稱為棧底（bottom）。不包含任何元素的棧稱為空棧。

1.1.1 棧的運算

? ? ? ?? ? ? ?

1.2 棧的存儲結構

1.2.1 棧的順序存儲

棧的順序存儲是指用一組地址連續的存儲單元依次存儲自棧頂到棧底的數據元素，同時附設置指針top指示棧頂元素的位置。順序存儲的棧也被稱為順序棧。這種存儲方式，需要預先定義或申請棧的存儲空間，所以順序棧的空間容量是有限的。在入棧的時候要判斷是否棧滿的情況。否則會出現上溢的異常。

1.2.2 棧的鏈式存儲

為了解決順序棧可能存在上溢的不足，可以用鏈表存儲棧中的元素。鏈式存儲的棧也被稱為鏈棧。元素的插入、刪除操作僅能在棧頂一端進行。因此可以不必設置頭節點。

1.2.3 棧的用途

棧的典型應用包括表達式求值、括號匹配等。在編程領域實現將遞歸過程轉變為非遞歸過程的處理中，棧可以起到重要作用。還可以實現數據的逆向輸出。?

2、隊列

2.1 隊列的定義

隊列是一種先進先出的線性表，它只允許在表的一端插入元素，在表的另一端刪除元素。在隊列中，允許插入元素的一端稱為隊尾（Rear），允許刪除元素的一端稱為隊頭（Front）

2.2 隊列的基本運算

? ? ? ?? ? ? ?

2.2 隊列的存儲結構

2.2.1 隊列的順序存儲

利用一組地址連續的存儲單元存放隊列中的元素。由于隊列中的元素插入和刪除限定在兩端進行，因此設置隊頭指針和隊尾指針需要分別指示當前的隊頭元素和隊尾元素。順序隊列的存儲空間是提前設定好的，因此隊尾指針會有一個上限值，達到上限就不能夠再入隊操作了。需要等隊頭有元素被移除。這個和日常買東西排隊是很相似的，比如買東西限定排隊人數為20人，如果當前已經排滿了，此時工作人員會阻止你的排隊行為，直到第一個買東西離開后，你就就可以繼續排隊了。判斷順序隊列位空隊列的方法是隊頭和隊尾的值相同。

注意：針對空隊列要能區分隊頭隊尾元素，可以通過標識位來區分隊頭和隊尾元素的不同。

2.2.2 隊列的鏈式存儲

隊列的鏈式存儲稱為鏈隊列。鏈隊列判斷是否位空隊列的條件是值相同并且均指向頭節點。

2.3 隊列的用途

隊列常用于需要排隊的場合，比如打印機打印文件、離散事件的計算機模擬、消息隊列、定時任務等方面。

IT技術分享社區

個人博客網站：https://programmerblog.xyz

文章推薦程序員效率：畫流程圖常用的工具程序員效率：整理常用的在線筆記軟件遠程辦公：常用的遠程協助軟件，你都知道嗎？51單片機程序下載、ISP及串口基礎知識硬件：斷路器、接觸器、繼電器基礎知識