[資料結構] 使用 C 語言:基於連結串列 (Linked List) 的雙向佇列 (Deque)

    雙向佇列的抽象資料結構

    雖然雙向佇列 (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 Email
    【追蹤本站】
    Facebook Facebook Twitter Plurk