開放原始碼技術文件網 基於連結串列 (Linked List) 的雙向佇列 (Deque)

最後修改日期為 APR 9, 2019

雙向佇列的抽象資料結構

雖然雙向佇列 (deque) 仍為受限制的線性資料結構,比起佇列,雙向佇列比較靈活一些,因為雙向佇列可以同時從頭端或尾端推入或推出資料。本文會以連結串列 (linked list) 實作雙向佇列。

雙向佇列

雙向佇列的抽象資料結構如下:

Q is a deque.

sub IsEmpty(Q): bool
(Optional) IsFull(Q): bool
(Optional) Size(Q): size >= 0
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

由此抽象資料結構可知,雙向佇列至少有以下行為:

  • IsEmpty:檢查雙向佇列是否為空
  • PeekFront:存取雙向佇列頭端的資料,不改變其大小
  • PeekRear:存取雙向佇列尾端的資料,不改變其大小
  • PushPushRear:將資料由頭端推入雙向佇列,其大小加 1
  • PopPopRear:將資料由頭端推出雙向佇列,其大小減 1
  • UnshiftPushFront:將資料由尾端推入雙向佇列,其大小加 1
  • ShiftPopFront:將資料由尾端推出雙向佇列,其大小減 1

以下行為則是選擇性的:

  • IsFull:檢查雙向佇列是否已滿
  • Size:回傳該雙向佇列的大小

雙向佇列的公開界面:

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

#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 */

雙向佇列可用的操作會比堆疊和佇列多,這是根據雙向佇列的抽象資料結構而來。

雙向佇列的型態宣告

由於我們使用串列實作雙向佇列,內部需要使用節點型態:

typedef struct node_t node_t;

struct node_t {
    int data;
    node_t *prev;
    node_t *next;
};

有節點型態後就可以宣告雙向佇列型態:

typedef struct deque_t deque_t;

struct deque_t {
    node_t *head;
    node_t *tail;
};

雙向佇列的建構函式

根據上述宣告實作建構函式如下:

deque_t * deque_new(void)
{
    deque_t *dq = \
        (deque_t *) malloc(sizeof(deque_t));
    if (!dq)
        return dq;
    
    dq->head = NULL;
    dq->tail = NULL;
    
    return dq;
}

雙向佇列的解構函式

若要釋放雙向佇列的記憶體,會用到兩個額外的指標 currtempcurr 一開始指向內部節點的頭端,temp 指向 curr 所在的節點:

釋放雙向佇列的記憶體 (步驟一)

curr 移往下一個節點後,即可釋放 temp 所在的節點:

釋放雙向佇列的記憶體 (步驟二)

反覆這個過程,就可以釋放所有的內部節點。實際上,會把這個過程寫在迴圈中,以利重覆執行。

將上述動作以 C 語言寫成解構函式:

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

    node_t *curr = ((deque_t *) self)->head;
    while (curr) {
        node_t *temp = curr;
        curr = curr->next;
        free(temp);
    }

    free(self);
}

要先逐一走訪內部節點並釋放後,再釋放佇列物件本身。

確認雙向佇列是否為空

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

bool deque_is_empty(const deque_t *self)
{
    assert(self);
    
    return !(self->head) ? true : false;
}

我們用指向頭端的指標是否為空來檢查佇列是否為空。

檢視雙向佇列頭端的資料

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

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

只要確認佇列不為空之後,直接存取頭端節點的資料即可。

檢視雙向佇列尾端的資料

PeekRear(Q) 也是採取類似的策略:

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

確認佇列不為空之後回傳尾端的資料即可。

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

要從尾端放入節點時,先將新節點 nodetail 節點相互連結:

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

接著再將指標 tail 重設到 node 即可:

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

將上述動作 (Push(Q)PushRear(Q)) 寫成 C 程式如下:

bool deque_push(deque_t *self, int data)  /*  1 */
{                                         /*  2 */
    node_t *node = node_new(data);        /*  3 */
    if (!node)                            /*  4 */
        return false;                     /*  5 */
    
    if (!(self->tail)) {                  /*  6 */
        self->head = node;                /*  7 */
        self->tail = node;                /*  8 */
    }                                     /*  9 */
    else {                                /* 10 */
        self->tail->next = node;          /* 11 */
        node->prev = self->tail;          /* 12 */
        self->tail = node;                /* 13 */
    }                                     /* 14 */
    
    return true;                          /* 15 */
}                                         /* 16 */

在推入資料時,要考慮佇列是否為空,兩者處理方式不同。

第 6 行至第 9 行代表 deque 為空的情境,這時候頭端和尾端都會指向同一個節點。

第 10 行至第 14 行代表 deque 不為空的情境,這時候將節點推向尾端即可。

node_new 的部分可參考以下程式碼:

static node_t * node_new(int data)
{
    node_t *node = \
        (node_t *) malloc(sizeof(node_t));
    if (!node)
        return node;
    
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    
    return node;
}

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

要從頭端放入節點時,先將新節點 nodehead 節點相互連結:

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

接著再將指標 head 重設到 node 即可:

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

上述動作 (UnshiftPushFront) 是從頭端推入資料,和前一節所介紹的 Push 採取類似的策略:

bool deque_unshift(deque_t *self, int data)  /*  1 */
{                                            /*  2 */
    node_t *node = node_new(data);           /*  3 */
    if (!node)                               /*  4 */
        return false;                        /*  5 */
    
    if (!(self->head)) {                     /*  6 */
        self->head = node;                   /*  7 */
        self->tail = node;                   /*  8 */
    }                                        /*  9 */
    else {                                   /* 10 */
        node->next = self->head;             /* 11 */
        self->head->prev = node;             /* 12 */
        self->head = node;                   /* 13 */
    }                                        /* 14 */
    
    return true;                             /* 15 */
}                                            /* 16 */

第 6 行至第 9 行代表 deque 為空的情境,這時候頭端和尾端都會指向相同的節點。

第 10 行至第 14 行代表 deque 不為空的情境,這時候將節點推入頭端即可。

這一節的實作和上一節的相似,讀者可相互比較。

從雙向佇列的尾端取出資料

若要從雙向佇列的尾端取出資料,要用一個額外的指標 curr,一開始先將 curr 指向 tail 節點:

從雙向佇列尾端取出資料 (步驟一)

將指標 tail 移往前一個節點後,就可以釋放指標 curr 所在的節點:

從雙向佇列尾端取出資料 (步驟二)

上述動作 (PopPopRear) 的 C 程式碼如下:

int deque_pop(deque_t *self)         /*  1 */
{                                    /*  2 */
    assert(!deque_is_empty(self));   /*  3 */

    int popped = self->tail->data;   /*  4 */
    
    if (self->head == self->tail) {  /*  5 */
        free(self->tail);            /*  6 */
        self->head = NULL;           /*  7 */
        self->tail = NULL;           /*  8 */
    }                                /*  9 */
    else {                           /* 10 */
        node_t *curr = self->tail;   /* 11 */
        self->tail = curr->prev;     /* 12 */
        free(curr);                  /* 13 */
        self->tail->next = NULL;     /* 14 */
    }                                /* 15 */
    
    return popped;                   /* 16 */
}                                    /* 17 */

推出佇列時,要考慮三種情境:(1) 佇列為空,(2) 佇列僅存單一節點,(3) 佇列有多個節點。本例在一開始時排除情境 (1),在情境 (2) 或 (3) 給予不同的處理方式。

當 deque 為空時,試圖從 deque 推出資料是不合法的 (invalid) 操作。所以我們在第 3 行中排除了 deque 為空的情境。

第 5 行至第 9 行代表 deque 只剩單一節點的情境,這時候將該節點釋放掉,頭端和尾端重新指向空指標。

第 10 行至第 15 行代表 deque 仍有多個節點的情境,這時候將尾端重新指向原節點的前一個節點,然後釋放掉尾端的節點。

從雙向佇列的頭端移出資料

若要從雙向佇列的頭端取出資料,要用一個額外的指標 curr,一開始先將 curr 指向 head 節點:

從雙向佇列頭端取出資料 (步驟一)

將指標 head 移往下一個節點後,就可以釋放指標 curr 所在的節點:

從雙向佇列頭端取出資料 (步驟二)

Shift(Q) (或 PopFront(Q)) 同樣也要考慮三種不同的情境:

int deque_shift(deque_t *self)       /*  1 */
{                                    /*  2 */
    assert(!deque_is_empty(self));   /*  3 */
    
    int popped = self->head->data;   /*  4 */

    if (self->head == self->tail) {  /*  5 */
        free(self->head);            /*  6 */
        self->head = NULL;           /*  7 */
        self->tail = NULL;           /*  8 */
    }                                /*  9 */
    else {                           /* 10 */
        node_t *curr = self->head;   /* 11 */
        self->head = curr->next;     /* 12 */
        free(curr);                  /* 13 */
        self->head->prev = NULL;     /* 14 */
    }                                /* 15 */
    
    return popped;                   /* 16 */
}                                    /* 17 */

當 deque 為空時,試圖從 deque 推出資料是非法的 (invalid),所以我們在第 3 行排除這個情境。

第 5 行至第 9 行代表 deque 僅存單一節點的情境。這時候會釋放掉該節點,然後將頭端和尾端重新指向空指標。

第 10 行至第 15 行代表 deque 還有多個節點的情境。這時候會將頭端重新指向原節點的次一個節點,然後釋放掉原節點。

本節的實作和上一節相似,讀者可將兩者相互比較。

在演算法上的效率

根據本範例的實作,可得到在演算法上的效率如下:

  • IsEmpty(Q)O(1)
  • PeekFront(Q)O(1)
  • PeekRear(Q)O(1)
  • Push(Q, data) (或 PushRear):O(1)
  • Unshift(Q, data) (或 PushFront):O(1)
  • Pop(Q) (或 PopRear):O(1)
  • Shift(Q) (或 PopFront):O(1)
分享本文
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Yahoo
追蹤本站
Facebook Facebook Twitter