堆疊與佇列
Stack & Queue
Apr 21, 2021
堆疊Stack
結構
Stack是一種後進先出(Last In First Out, LIFO)的實現，其結構包含:
- 資料(data): 可以根據需求是任意的資料型態，如int, char…等
- 頂端(top): 一般型態為int，初始值可以是0或-1。只是陣列第一項的索引值會是0，所以通常會把top初始化為-1，不過只要自己注意有定義好就可以了。
操作
在結構的操作上可以把資料存進堆疊裡(通常稱作Push)，也可以將資料取出(通常稱作Pop):
雖然 push, pop只是習慣叫法，沒有一定要這樣用，但這麼做可以讓程式更容易閱讀，一眼就看出是在操作 stack。
- Push: 將資料放在堆疊的最上面，也就是說先前放的會在底下。
- Pop: 取出堆疊中最上面的那筆資料。
範例
以下為利用array實作的stack以及相關函式的宣告範例
應用
四則運算計算機
佇列Queue
結構
Queue為一種先進先出(First In First Out, FIFO)的實現，生活中很常見到Queue的例子，如台灣人很愛的排隊(x)。其結構包含:
- data: 可以根據需求是任意的資料型態。
- front: 一般型態為int，代表第一筆資料所在的索引值(index)。
- rear: 一般型態為int，代表最後一筆資料所在的索引值。
操作
在結構的操作上可以把資料存進佇列裡(通常稱作enqueue)，也可以將資料取出(通常稱作dequeue):
enqueue, dequeue一樣只是習慣叫法，沒有一定要這樣用，
- enqueue: 將資料從佇列尾巴填入，若是第一筆資料，則會排在佇列的最前面。
- dequeue: 取出排在佇列最前端的那一筆資料。
範例
以下為C語言利用array實作的circular queue以及相關函式的宣告範例。
延伸 — Circular Queue
將整個佇列空間的頭尾相接，讓front與end在環之中消長，可以重複使用記憶體空間。
#define MAX 100
...
q.front == q.rear // empty
q.rear+1 = q.front // overflow
...
q.front = (q.front+1) % MAX // 讓front在0-99之間循環第四行+1是為了避免empty和overflow的條件相同(ambiguous)，在判斷上產生麻煩。
卻也因此浪費掉了一個元素的記憶體空間，如果資料本身不大倒還沒關係，但如果資料本身是一個結構，一個元素就佔了不少空間。那麼，這時候可以多用一個counter來代表資料的位置。
if (counter == MAX) // overflow
