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

[資料結構] 使用 C 語言:以連結串列 (Linked List) 為基礎的佇列 (Queue)

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

    佇列的抽象資料結構

    佇列 (queue) 是另一種受限制的線性資料結構。其操作方式為從尾端推入,從頭端推出,是一種 FIFO (First-In, First-Out) 的資料結構。在現實生活中,佇列就像是在大賣場排隊結帳的人,先排隊的人可以先結帳。本文以串列實作佇列。

    佇列

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

    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
    

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

    • IsEmpty(Q):確認佇列是否為空
    • Peek(Q):檢視佇列頭端的資料,不改變佇列大小
    • Enqueue(Q, data):從佇列尾端推入資料,佇列長度加 1
    • Dequeue(Q):從佇列頭端推出資料,佇列長度減 1

    以下方法是選擇性的:

    • IsFull(Q):檢查佇列是否已滿
    • Size(Q):回傳佇列的大小
    • PeekRear(Q):存取佇列尾端的資料,不改變佇列大小

    (影音教學) 佇列的基本操作

    以下影片會拆解一些佇列常見的基本操作:

    影片的內容是選擇性的,不影響文章的閱讀,有需要的讀者請自行觀看。

    佇列的類別宣告

    如同其他的串列結構,我們會用輔助性的 node_t 類別來儲存資料:

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

    以等效的 C 程式碼實作如下:

    typedef struct node_t node_t;
    
    struct node_t {
        int data;
        node_t *prev;
        node_t *next;
    };
    
    typedef struct queue_t queue_t;
    
    struct queue_t {
        node_t *head;
        node_t *tail;
    };

    佇列的建構函式

    以下是以 C 程式碼實作的建構函式:

    queue_t * queue_new(void)
    {
        queue_t *q = malloc(sizeof(queue_t));
        if (!q) {
            return q;
        }
        
        q->head = NULL;
        q->tail = NULL;
        
        return q;
    }

    佇列的解構函式

    為了要釋放佇列的內部節點,我們需要額外的兩個指標。curr 一開始指向內部節點的頭端,而 temp 是暫存值,指向 curr 所在的節點:

    釋放佇列節點 (步驟一)

    當我們把 curr 移往下一個節點時,就可以把 temp 所在的節點釋放掉:

    釋放佇列節點 (步驟二)

    重覆這個動作,就可以把所有的節點釋放掉。我們會把這個動作寫在迴圈裡,用來自動執行。

    將上述動作寫到以下解構函式中,用來釋放記憶體:

    void queue_delete(void *self)
    {
        if (!self)
            return;
        
        node_t *curr = ((queue_t *) self)->head;
        while (curr) {
            node_t *temp = curr;
            curr = curr->next;
            free(temp);
        }
        
        free(self);
    }

    要先釋放佇列的內部節點,再釋放佇列物件本身。

    確認佇列是否為空

    以下是 IsEmpty 的虛擬碼:

    Q is a queue.
    
    sub IsEmpty(Q): bool
        return Q.head == null
    

    我們的做法是檢查頭端的指標是否為空。如果在類別中有存放佇列大小的欄位,也可用該欄位檢查佇列大小。

    以等效的 C 程式碼撰寫如下:

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

    檢視佇列頭端的資料

    以下是 Peek 的虛擬碼:

    Q is a queue.
    
    sub Peek(Q): data
        assert(not IsEmpty(Q))
    
        return Q.head.data
    

    在我們的實作中,我們會確認佇列不為空,之後直接存取頭端節點的資料即可。

    以下是等效的 C 語言實作:

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

    將資料放入佇列

    要將資料放入節點時,先建立新的資料節點 node,將 tail 節點和其相接:

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

    再將 tail 重新把向 node 節點即可:

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

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

    Q is a queue.
    
    sub Enqueue(Q, data): void
        node <- node(data)
        
        if (Q.head == null) then
            Q.head <- node
            Q.tail <- node
            return
        end if
        
        Q.tail.next <- node
        node.next <- Q.tail
        Q.tail <- node
    

    在推入資料時,要考慮佇列是否為空,兩個情境的處理方式相異。

    以下是等效的 C 語言實作:

    bool queue_enqueue(queue_t *self, int data)
    {
        assert(self);
    
        node_t *node = node_new(data);
        if (!node)
            return false;
        
        if (!(self->head)) {
            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;
    }

    將資料移出佇列

    要將資料節點移出佇列時,需要使用額外的指標 curr,該指標指向 head 所在的節點:

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

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

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

    將上述動作 (Dequeue) 寫成以下虛擬碼:

    Q is a queue.
    
    sub Dequeue(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
        end if
    
        return popped
    

    將資料推出佇列時,有三個情境:(1) 佇列為空,(2) 佇列頭端和尾端指向同一個節點,(3) 佇列包含多個節點。本範例排除情境 (1),根據情境 (2) 或 (3) 給予相對應的處理。

    以下是等效的 C 程式碼:

    int queue_dequeue(queue_t *self)
    {
        assert(!queue_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);
        }
        
        return popped;
    }

    在演算法上的效率

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

    • IsEmpty(Q): O(1)
    • Peek(Q): O(1)
    • Enqueue(Q, data): O(1)
    • Dequeue(Q): O(1)
    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
    【贊助商連結】
    標籤: DATA STRUCTURES
    【贊助商連結】
    【分類瀏覽】