開放原始碼技術文件網 以陣列 (Array) 為基礎的佇列 (Queue)

最後修改日期為 SEP 23, 2021

佇列的抽象資料結構

在本文中,我們會實作佇列 (queue),但內部實作不是用這類教材常見的串列 (linked list),而是使用陣列 (array),讀者可以和先前的文章比較一下。其 ADT 如下:

Q is a queue.

sub IsEmpty(Q): bool
(Optional) IsFull(Q): bool
(Optional) Size(Q): sz
sub Peek(Q): data
(Optional) PeekRear(Q): data
sub Enqueue(Q, data): void
sub Dequeue(Q): data

我們採用和前文相同的抽象資料結構,故不重覆說明。

佇列的公開界面

以下是佇列的公開界面:

#ifndef QUEUE_H
#define QUEUE_H

#ifndef __cplusplus
    #include <stdbool.h>
#endif

typedef struct queue_t queue_t;

#ifdef __cplusplus
extern "C" {
#endif

queue_t * queue_new(void);
void queue_delete(void *self);
bool queue_is_empty(const queue_t *self);
int queue_peek(const queue_t *self);
bool queue_enqueue(queue_t *self, int data);
int queue_dequeue(queue_t *self);

#ifdef __cplusplus
}
#endif

#endif  /* QUEUE_H */

基本上,公開界面的部分是雷同的,因為我們只是換掉內部實作。

佇列的型態宣告

以陣列實作佇列時,其內部構造如下:

佇列陣列

對應上述構造,宣告如下的型態:

typedef struct queue_t queue_t;

struct queue_t {
    size_t size;
    size_t capacity;
    size_t head;
    size_t tail;
    int *elements;
};

在此類別中,有兩個屬性和佇列的大小相關,一個是佇列當下的大小 size,一個是佇列的最大容量 capacity。另外有兩個和佇列頭、尾端位置相關的屬性,由於我們內部以陣列儲存元素,故頭、尾端是索引值而非指標。

佇列的建構函式

在此類別宣告下的建構函式的參考實作如下:

queue_t * queue_new(void)
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return q;

    q->size = 0;
    /* We start with a small capacity intentionally
        to test queue expansion. */
    q->capacity = 2;

    q->head = 0;
    q->tail = 0;
    q->elements = malloc(q->capacity * sizeof(int));
    if (!(q->elements)) {
        free(q);
        q = NULL;
        return q;
    }

    return q;
}

佇列的解構函式

以下是 C 語言的解構函式:

void queue_delete(void *self)
{
    if (!self)
        return;

    int *elements = ((queue_t *) self)->elements;
    if (elements)
        free(((queue_t *) self)->elements);

    free(self);
}

要先釋放佇列內部的陣列後,再釋放佇列物件本身。由於此佇列內部以陣列儲存,是整塊的記憶體,不需使用迴圈。

檢查佇列是否為空

IsEmpty(Q) 的 C 程式碼如下:

bool queue_is_empty(const queue_t *self)
{
    assert(self);
    
    return self->size == 0;
}

直接檢查 size 屬性是否為零即可。

檢視佇列頭端的資料

Peek(Q) 的 C 程式碼如下:

int queue_peek(const queue_t *self)
{
    assert(!queue_is_empty(self));
    
    return self->elements[self->head];
}

在本文中,我們用 head 取代指標,指向佇列的頭端所在的位置。

將資料放入佇列

要將資料放入佇列時,先將 tail 移動:

將資料放入佇列陣列 (步驟一)

之後再放入新的資料即可:

將資料放入佇列陣列 (步驟二)

有些細心的讀者可能會擔心容量爆掉的情境,實際上在放入資料前會視需求擴展容量。

將上述過程 (Enqueue) 寫成 C 程式碼如下:

bool queue_enqueue(queue_t *self, int data)
{
    if (!queue_expand(self)) {
        return false;
    }
    
    if (self->size == 0) {
        self->elements[self->tail] = data;
        self->size += 1;
        return true;
    }

    self->tail = (self->tail + 1) % self->capacity;
    self->elements[self->tail] = data;
    self->size += 1;
    
    return true;
}

一開始要先視需求擴展容量,下文會說明 queue_expand() 部分的程式碼。

在推入佇列時,要考慮目前佇列是否為空,兩者的處理方式不同,否則 tail 指向的位置會差 1,讀者可試著自行追蹤虛擬碼即可了解。

要擴展佇列時,會先建立一個新的陣列,再將原陣列的資料逐一拷貝到新陣列上:

擴展佇列陣列容量

新的容量是原陣列大小的兩倍。

以下是 queue_expand() 部分的 C 程式碼:

static bool queue_expand(queue_t *self)
{
    if (self->size < self->capacity) {
        return true;
    }
    
    int *oldArr = self->elements;
    self->capacity = self->size * 2;
    int *newArr = malloc(self->capacity * sizeof(int));
    if (!newArr) {
        return false;
    }
    
    size_t sz = 0;
    size_t i = self->head;
    size_t j = self->head;
    while (sz < self->size) {
        newArr[i] = oldArr[j];
        
        i = (i + 1) % self->capacity;
        j = (j + 1) % self->size;
        sz += 1;
    }
    
    self->elements = newArr;
    self->tail = (self->head + self->size - 1) % self->capacity;
    free(oldArr);
    
    return true;
}

我們同樣用環狀陣列的手法拷貝元素,要注意 ij 的平移距離不同,因 old_arrnew_arr 的大小不同。

將資料移出佇列

要將資料移出佇列時,先移動 head

將資料移出佇列陣列 (步驟一)

其實這樣就完成了。日後新增節點時會自動覆蓋掉該位置的資料:

將資料移出佇列陣列 (步驟二)

將上述動作 (Dequeue) 寫成 C 程式碼:

int queue_dequeue(queue_t *self)
{
    assert(!queue_is_empty(self));
    
    int popped = self->elements[self->head];
    self->head = (self->head + 1) % self->capacity;
    self->size -= 1;
    
    return popped;
}

由於推出資料時,head 是向後推移,故其值為加 1 而非減 1,同樣要用環狀陣列的手法平移。

在演算法上的效率

根據本文的實作,得到的演算法效率如下:

  • IsEmpty: O(1)
  • Peek: O(1)
  • Enqueue: amortized O(1)
  • Dequeue: O(1)

如同先前堆疊的例子,在執行 Enquene 時若陣列有擴張,其效率為 O(n),但以攤平分析法 (amortized analysis) 來分析可知其效率為 O(1)

分享本文
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Yahoo
追蹤本站
Facebook Facebook Twitter