【在主畫面加入捷徑】
       
【選擇語系】
繁中 简中

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

【分享本文】
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
【贊助商連結】

    雙向佇列的抽象資料結構

    雖然雙向佇列 (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:回傳該雙向佇列的大小

    雙向資料結構的類別宣告

    如果要以串列實作,可參考以下類別宣告:

    class Node:
        data <- none
        prev <- null
        next <- null
        
    class Deque:
        head <- null
        tail <- null
    

    以等效的 C 語言改寫如下:

    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 = 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 is a deque.
    
    sub IsEmpty(Q): bool
        return Q.head == null
    

    我們用指向頭端的指標是否為空來檢查佇列是否為空。以等效的 C 語言實作如下:

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

    檢視雙向佇列頭端的資料

    PeekFront 的虛擬碼如下:

    Q is a deque.
    
    sub PeekFront(Q): data
        assert(not IsEmpty(Q))
        
        return Q.head.data
    

    只要確認佇列不為空之後,直接存取頭端節點的資料即可。改寫成 C 程式碼如下:

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

    檢視雙向佇列尾端的資料

    PeekRear 也是採取類似的策略:

    Q is a deque.
    
    sub PeekRear(Q): data
        assert(not IsEmpty(Q))
        
        return Q.tail.data
    

    確認佇列不為空之後回傳尾端的資料即可。以 C 語言實作如下:

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

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

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

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

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

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

    將上述動作 (PushPushRear) 寫成虛擬碼如下:

    Q is a deque.
    
    sub Push(Q, data): void
        node <- node(data)
        
        if Q.tail == null then
            Q.head <- node
            Q.tail <- node
            end sub
        end if
        
        Q.tail.next <- node
        node.prev <- Q.tail
        Q.tail <- node
    

    在推入資料時,要考慮佇列是否為空,兩者處理方式不同。以 C 語言實作如下:

    bool deque_push(deque_t *self, int data)
    {
        node_t *node = node_new(data);
        if (!node)
            return false;
        
        if (!(self->tail)) {
            self->head = node;
            self->tail = node;
        }
        else {
            self->tail->next = node;
            node->prev = self->tail;
            self->tail = node;
        }
        
        return true;
    }

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

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

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

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

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

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

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

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

    Q is a deque.
    
    sub Unshift(Q, data): void
        node <- node(data)
        
        if Q.head == null then
            Q.head <- node
            Q.tail <- node
        else
            node.next <- Q.head
            Q.head.prev <- node
            Q.nead <- node    
        end if
    

    以 C 語言實作的實例如下:

    bool deque_unshift(deque_t *self, int data)
    {
        node_t *node = node_new(data);
        if (!node)
            return false;
        
        if (!(self->head)) {
            self->head = node;
            self->tail = node;
        }
        else {
            node->next = self->head;
            self->head->prev = node;
            self->head = node;
        }
        
        return true;
    }

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

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

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

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

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

    上述動作 (PopPopRear) 的虛擬碼如下:

    Q is a deque.
    
    sub Pop(Q): data
        assert not IsEmpty(Q)
        
        popped <- Q.tail.data
        
        if Q.head == Q.tail then
            delete Q.tail
            Q.head <- null
            Q.tail <- null
        else
            curr <- Q.tail
            Q.tail <- curr.prev
            delete curr
            Q.tail.next <- null
        end if
        
        return popped
    

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

    以 C 語言實作如下:

    int deque_pop(deque_t *self)
    {
        assert(!deque_is_empty(self));
    
        int popped = self->tail->data;
        
        if (self->head == self->tail) {
            free(self->tail);
            self->head = NULL;
            self->tail = NULL;
        }
        else {
            node_t *curr = self->tail;
            self->tail = curr->prev;
            free(curr);
            self->tail->next = NULL;
        }
        
        return popped;
    }

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

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

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

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

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

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

    Q is a deque.
    
    sub Shift(Q): data
        assert(not IsEmpty(Q))
        
        popped <- Q.head.data
        
        if Q.head == Q.tail then    
            delete Q.head
            Q.head <- null
            Q.tail <- null
        else
            curr <- Q.head
            Q.head <- curr.next
            delete curr
            Q.head.prev <- null
        end if
        
        return popped
    

    將前述虛擬碼以 C 語言實作如下:

    int deque_shift(deque_t *self)
    {
        assert(!deque_is_empty(self));
        
        int popped = self->head->data;
    
        if (self->head == self->tail) {
            free(self->head);
            self->head = NULL;
            self->tail = NULL;
        }
        else {
            node_t *curr = self->head;
            self->head = curr->next;
            free(curr);
            self->head->prev = NULL;
        }
        
        return popped;
    }

    在演算法上的效率

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

    • 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
    【贊助商連結】
    標籤: DATA STRUCTURES
    【贊助商連結】
    【分類瀏覽】