開放原始碼技術文件網 以陣列 (Array) 實做雙向佇列 (Deque)

最後修改日期為 APR 29, 2019

雙向佇列的抽象資料結構

在本文中,我們仍然實作雙向佇列,但內部改以陣列來實作。

以下是此雙向佇列的抽象資料結構:

Q is a deque.

sub IsEmpty(Q): bool
(Optional) IsFull(Q): bool
(Optional) Size(Q): sz
sub PeekFront(Q): data
sub PeekRear(Q): data
sub Push(Q, data): void
sub Pop(Q): data
sub Unshift(Q, data): void
sub Shift(Q): data

基本上抽象資料結構是相同的,故不重覆說明。

雙向佇列的公開界面

以下是雙向佇列的公開界面:

#ifndef DEQUE_H
#define DEQUE_H

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

typedef struct deque_t deque_t;

#ifdef __cplusplus
extern "C" {
#endif

deque_t * deque_new(void);
void deque_delete(void *self);
bool deque_is_empty(const deque_t *self);
int deque_peek_front(const deque_t *self);
int deque_peek_rear(const deque_t *self);
bool deque_push(deque_t *self, int data);
int deque_pop(deque_t *self);
bool deque_unshift(deque_t *self, int data);
int deque_shift(deque_t *self);

#ifdef __cplusplus
}
#endif

#endif  /* DEQUE_H */

基本上,和前一篇文章的雙向佇列的公開界面雷同,因為我們只抽換掉內部實作。

雙向佇列的型態宣告

以陣列為基礎的雙向佇列的圖示如下:

以陣列實作的雙向佇列

以陣列為基礎的類別宣告的 C 程式碼如下:

typedef struct deque deque_t;

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

雙向佇列的建構函式

以 C 語言實作建構函式如下:

deque_t * deque_new(void)
{
    deque_t *dq = malloc(sizeof(deque_t));
    if (!dq)
        return dq;
    
    dq->size = 0;
    dq->capacity = 2;
    dq->head = 0;
    dq->tail = 0;
    
    dq->elements = malloc(dq->capacity * sizeof(int));
    if (!(dq->elements)) {
        free(dq);
        dq = NULL;
        return dq;
    }

    return dq;
}

一開始的 capacity 只要大於等於 2 即可;一般使用下可設 16,此處故意設 2 是為了看佇列擴張時是否會引發錯誤。

雙向佇列的解構函式

以下是 C 語言的雙向佇列解構函式:

void deque_delete(void *self)
{
    if (!self) {
        return;
    }
    
    int *elements = ((deque_t *) self)->elements;
    if (elements) {
        free(((deque_t *) self)->elements);
    }

    free(self);
}

先釋放內部陣列後,再釋放佇列物件本身。

確認雙向佇列是否為空

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

bool deque_is_empty(const deque_t *self)
{
    assert(self);
    
    return self->size <= 0;
}

在我們的實作中,會儲存佇列大小的資訊,要檢查佇列是否為空時檢查此屬性即可。

檢視雙向佇列頭端的資料

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

int deque_peek_front(const deque_t *self)
{
    assert(!deque_is_empty(self));
    
    return self->elements[self->head];
}

我們的 head 以數字做為索引值 (index value),用來取代指標。

檢視雙向佇列尾端的資料

PeekRear(Q) 的虛擬碼如下:

int deque_peek_rear(const deque_t *self)
{
    assert(!deque_is_empty(self));
    
    return self->elements[self->tail];
}

PeekFront(Q) 類似,以數字做為索引來取代指標。

將資料推入雙向佇列的尾端

要將資料推入雙向佇列尾端前,要先移動 tail,如下圖:

將資料推入雙向佇列 (步驟一)

接著將資料寫入即可:

將資料推入雙向佇列 (步驟二)

Push (或 PushRear) 的 C 程式碼如下:

bool deque_push(deque_t *self, int data)
{
    if (!deque_extend(self)) {
        return false;
    }
    
    if (deque_is_empty(self)) {
        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;
}

一開始要視需求擴張雙向佇列,我們會在下文介紹 deque_extend() 函式的實作。

要注意佇列為空和非空時的處理方法不同,佇列為空時,索引值不會跳動,但佇列大小會加 1,之後則索引值和佇列大小皆會加 1。

擴張雙向佇列內部的陣列的原理是建立一個新的陣列後,將資料逐一拷貝到新的陣列上。如下圖:

擴張以陣列為基礎的雙向佇列

一般會把新的陣列的最大容量設為原本陣列的大小的兩倍。

deque_extend() 部分的 C 程式碼如下:

static bool deque_extend(deque_t *self)
{
    if (self->size < self->capacity) {
        return true;
    }
    
    int *old_arr = self->elements;
    self->capacity = self->size * 2;
    int *new_arr = malloc(self->capacity * sizeof(int));
    if (!new_arr) {
        return false;
    }
    
    size_t sz = 0;
    size_t i = self->head;
    size_t j = self->head;
    while (sz < self->size) {
        new_arr[i] = old_arr[j];
        
        i = (i + 1) % self->capacity;
        j = (j + 1) % self->size;
        sz += 1;
    }

    self->elements = new_arr;
    free(old_arr);
    
    return true;
}

重點在佇列擴張時,新的內部陣列的大小是舊的內部陣列的兩倍大,處理索引值的分母相異。

將資料推入雙向佇列的頭端

若要將資料推入頭端,先移動 head。如下圖:

將資料推入雙向佇列 (步驟一)

之後再將資料寫入即可。如下圖:

將資料推入雙向佇列 (步驟二)

以下是 Unshift(Q) (或 PushFront(Q)) 的虛擬碼:

bool deque_unshift(deque_t *self, int data)
{
    if (!deque_extend(self))
        return false;

    if (deque_is_empty(self)) {
        self->elements[self->head] = data;
    }
    else {
        self->head = self->head == 0 ? self->capacity - 1 : self->head - 1;
        self->elements[self->head] = data;
    }
    
    self->size += 1;

    return true;
}

雖然佇列大小變大,但頭端是往回走,故要減 1 而非加 1,同樣要注意索引值為 0 時的處理方法。

將資料從雙向佇列尾端推出

將尾端資料拷貝出來後,移動 tail。如下圖:

將資料移出雙向佇列的尾端 (步驟一)

其實在移動完 tail 後,整個動作就算完成了。之後在寫入新資料時會自動覆蓋掉原本的資料。如下圖:

將資料移出雙向佇列的尾端 (步驟二)

以下是 Pop(Q) (或 PopRear(Q)) 的虛擬碼:

int deque_pop(deque_t *self)
{
    assert(!deque_is_empty(self));
    
    int popped = self->elements[self->tail];
    self->tail = self->tail == 0 ? self->capacity - 1 : self->tail - 1;
    self->size -= 1;
    
    return popped;
}

由於索引值不能為負,注意當索引值為 0 時的處理方式。

將資料從雙向佇列頭端推出

將頭端資料拷貝出來後,移動 head。如下圖:

將資料移出雙向佇列的頭端 (步驟一)

其實在移動完 head 後,整個動作就算完成了。之後在寫入新資料時會自動覆蓋掉原本的資料。如下圖:

將資料移出雙向佇列的頭端 (步驟二)

以下是 Shift(Q) (或 PopFront(Q)) 的虛擬碼:

int deque_shift(deque_t *self)
{
    assert(!deque_is_empty(self));

    int popped = self->elements[self->head];
    self->head = (self->head + 1) % self->capacity;
    self->size -= 1;
    
    return popped;
}

雖然佇列大小變小,但索引是往後推,故索引值是加 1 而非減 1。

在演算法上的效率

此範例程式在演算法上的效率如下:

  • IsEmpty(Q)O(1)
  • PeekFront(Q)O(1)
  • PeekRear(Q)O(1)
  • Push(Q, data):amortized O(1)
  • Unshift(Q, data):amortized O(1)
  • Pop(Q)O(1)
  • Shift(Q)O(1)

佇列在擴張時,其效率為 O(n),若未擴張,其效率為 O(1);經攤平分析法 (amortized analysis) 可知其攤平後的效率為 O(1)

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