堆疊與佇列

Stack & Queue

堆疊Stack

https://en.wikipedia.org/wiki/File:Data_Queue.svg

結構

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

https://en.wikipedia.org/wiki/File:Data_Queue.svg

結構

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

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

--

--

Qertile 郭泰爾
Qertile 郭泰爾

Written by Qertile 郭泰爾

學習路上順便做點筆記留下痕跡OUO,怕以後忘了曾經所學的這些知識。

No responses yet