目錄
前言
一、堆疊
1.堆疊的定義及其運算
1）堆疊的定義
2）堆疊的運算
2.堆疊的存盤表示
1）堆疊的順序存盤結構
2）堆疊的鏈式存盤結構
二、佇列
1.佇列的定義及其運算
1）佇列的定義
2）佇列的運算
2.順序回圈佇列
3.鏈佇列
小結
前言
本篇文章給小伙伴們分享資料結構的第3章——堆疊和佇列，本文主要介紹堆疊和佇列的基本概念，不會涉及復雜的演算法和代碼，堆疊和佇列是非常重要的兩種線性結構，應用也非常廣，所以建議小伙伴們最好要掌握這部分內容，
一、堆疊
1.堆疊的定義及其運算
1）堆疊的定義
堆疊是限定在表的一端進行插入和洗掉運算的線性表，通常將插入、洗掉的一端稱為堆疊頂（top），另一端稱為堆疊底（bottom），
根據堆疊的上述定義，堆疊的元素只能按照后進先出的原則修改，因此，堆疊又稱為后進先出的線性表，簡稱LIFO表，
2）堆疊的運算
堆疊的運算主要有以下幾種：
- 置空堆疊 InitStack(&S)：構造一個空堆疊S，
- 判堆疊空 StackEmpty(S)：若堆疊S為空堆疊，則回傳TRUE，否則回傳FALSE，
- 判堆疊滿 StackFull(S)：若堆疊S為滿堆疊，則回傳TRUE，否則回傳FALSE，
- 進堆疊（又稱入堆疊或插入）Push(&S,x)：將元素 x 插入S堆疊的堆疊頂，
- 退堆疊（又稱出堆疊或洗掉）Pop(&S)：若堆疊S為非空，則將S的堆疊頂元素洗掉，并回傳堆疊頂元素，
- 取堆疊頂元素 GetTop(S)：若S堆疊為非空，則回傳堆疊頂元素，但不改變堆疊的狀態，
2.堆疊的存盤表示
1）堆疊的順序存盤結構
堆疊的順序存盤結構稱為順序堆疊，由于堆疊是運算受限的線性表，因此線性表的存盤結構對堆疊也適用，類似于順序表的定義，順序堆疊也是用陣列實作的，因為堆疊底位置是固定不變的，故可以將堆疊底位置設定在陣列的最低端（即下標為0）；堆疊頂位置是隨著進堆疊和退堆疊操作而變化的，故需用一個堆疊頂指標top來指示當前堆疊頂位置，
由于順序堆疊必須預先分配存盤空間，因此可能會產生溢位和空間浪費的問題，為解決這個問題，我們可以讓多個堆疊共享存盤空間，這樣可以相互調節，既節約了空間，又可以降低發生溢位的頻率，
怎樣使多個堆疊共享存盤空間呢？當程式中同時使用兩個堆疊時，可以將兩個堆疊的堆疊底分別設在順序存盤空間兩端，讓兩個堆疊頂各自向中間延伸，當一個堆疊中元素較多進而使用空間超過共享空間一半時，只要另一個堆疊元素不多，就可以占用另一個堆疊的部分存盤空間，只有當整個共享空間被兩個堆疊占滿時（即兩堆疊頂相遇），才會產生溢位，
2）堆疊的鏈式存盤結構
堆疊的鏈式存盤結構稱為鏈堆疊，它是運算受限的單鏈表，其插入和洗掉操作僅限制在表頭位置上（堆疊頂）進行，因此不必設定頭結點，將單鏈表的頭指標head改為堆疊頂指標top即可，
二、佇列
1.佇列的定義及其運算
1）佇列的定義
佇列也是一種操作受限的線性表，它只允許在表的一端進行元素插入，而在另一端進行元素洗掉，允許插入的一端稱為隊尾（rear），允許洗掉的一端稱為隊頭（front），
在佇列中，通常元素插入稱為入隊，元素洗掉稱為出隊，佇列的概念與現實生活中的排隊相似，新來的成員總是加入隊尾，排在佇列最前面的總是最先離開佇列，即先進先出，因此又稱佇列為先進先出（FIFO）表，
2）佇列的運算
佇列的操作運算與堆疊類似，主要有以下幾種：
- 置空佇列 InitQueue(Q)，構造一個空佇列Q，
- 判隊空 QueueEmpty(Q)，若Q為空佇列，則回傳TRUE，否則回傳FALSE，
- 入佇列 EnQueue(Q, x)，若佇列不滿，則將資料 x 插入到Q的隊尾，
- 出佇列 DeQueue(Q)，若佇列不空，則洗掉隊頭元素，并回傳該元素，
- 取隊頭 GetFront(Q)，若佇列不空，則回傳隊頭元素，
2.順序回圈佇列
佇列的順序存盤結構稱為順序佇列，它也是利用一塊連續的存盤單元存放佇列中的元素，由于隊頭和隊尾位置是變化的，因此需要設定兩個指標 front 和 rear 分別指示隊頭和隊尾元素在表中的位置，
為了充分利用陣列空間，克服上溢，可將陣列空間想象為一個環狀空間，并稱這種環狀陣串列示的佇列為回圈佇列，回圈佇列中，出隊元素的空間可以重新被利用，所以，一般情況下真正實用的順序佇列是回圈佇列，
判斷回圈佇列是“空”還是“滿”，常用方法一般有三種：
- 另設一個標志位，以區別佇列是“空”還是“滿”，
- 設定一個計數器記錄佇列中元素個數，
- 少用一個元素空間，約定入隊前，測驗尾指標在回圈意義下加1后是否等于頭指標，若相等則認為佇列滿，即尾指標Q.rear所指向的單元始終為空，
3.鏈佇列
佇列的鏈式存盤結構稱為鏈佇列，它是一種限制在表頭洗掉和表尾插入操作的單鏈表，顯然，僅有單鏈表的頭指標不便在表尾作插入操作，為此再增加一個尾指標，使其指向鏈表上的最后一個結點，一個鏈佇列由一個頭指標和一個尾指標唯一確定，
小結
堆疊和佇列是兩種十分重要的線性結構，它們的邏輯結構和前面介紹的線性表完全相同，只是對其操作運算有一定的限制，故又稱它們為操作受限的線性表，堆疊和佇列結構在各種程式設計中被廣泛應用，
ps：博主創作不易，喜歡這篇文章的老鐵們點個贊吧！(#^.^#)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/317834.html
標籤：其他