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

[資料結構] 使用 C 語言:以陣列 (Array) 為基礎的佇列 (Queue)

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

    佇列的抽象資料結構

    在本文中,我們會實作佇列 (queue),但內部實作不是用這類教材常見的串列 (linked list),而是使用陣列 (array),讀者可以和先前的文章比較一下。其 ADT 如下:

    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
    

    我們採用和前文相同的抽象資料結構,故不重覆說明。

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

    我們在此處附上佇列相關的教學:

    這個影片會拆解一些佇列的基本操作,有興趣的讀者可以看看。這影片的內容和文章是獨立的,不影響文章的閱讀。

    佇列的類別宣告

    以陣列實作佇列時,其內部構造如下:

    佇列陣列

    對應上述構造,宣告如下的類別:

    class Queue:
        size <- 0
        capacity <- n
        head <- 0
        tail <- 0
        elements <- a zero-based array with size == capacity
    

    在此類別中,有兩個屬性和佇列的大小相關,一個是佇列當下的大小 size,一個是佇列的最大容量 capacity。另外有兩個和佇列頭、尾端位置相關的屬性,由於我們內部以陣列儲存元素,故頭、尾端是索引值而非指標。

    以等效的 C 語言宣告如下:

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

    佇列的建構函式

    在此類別宣告下的建構函式的參考實作如下:

    queue_t * queue_new(void)
    {
        queue_t *q = malloc(sizeof(queue_t));
        if (!q)
            return q;
    
        q->size = 0;
        q->capacity = 16;
        q->head = 0;
        q->tail = 0;
        q->elements = malloc(q->capacity * sizeof(int));
        if (!(q->elements)) {
            free(q);
            q = NULL;
            return q;
        }
    
        return q;
    }

    佇列的解構函式

    以下是 C 語言的解構函式:

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

    要先釋放佇列內部的陣列後,再釋放佇列物件本身。由於此佇列內部以陣列儲存,是整塊的記憶體,不需使用迴圈。

    檢查佇列是否為空

    IsEmpty 的虛擬碼如下:

    Q is a queue.
    
    sub IsEmpty(Q): bool
        return Q.size == 0
    

    直接檢查 Q.size 屬性是否為零即可。等效的 C 語言實作如下:

    bool queue_is_empty(const queue_t *self)
    {
        assert(self);
    
        return self->size == 0;
    }

    檢視佇列頭端的資料

    Peek 的虛擬碼如下:

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

    在本文中,我們用 Q.head 取代指標,指向佇列的頭端所在的位置。換成等效的 C 語言實作如下:

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

    將資料放入佇列

    要將資料放入佇列時,先將 tail 移動:

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

    之後再放入新的資料即可:

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

    有些細心的讀者可能會擔心容量爆掉的情境,實際上在放入資料前會視需求擴展容量。

    將上述過程 (Enqueue) 寫成虛擬碼如下:

    Q is a queue.
    
    sub Enqueue(Q, data): void
        Expand(Q)
        
        if Q.size > 0 then
            Q.tail <- (Q.tail + 1) % Q.capacity
        end if
    
        Q.elements[Q.tail] <- data
        q.size += 1
    

    一開始要先視需求擴展容量,下文會說明 Expand(Q) 部分的程式碼。

    在推入佇列時,要考慮目前佇列是否為空,兩者的處理方式不同,否則 tail 指向的位置會差 1,讀者可試著自行追蹤虛擬碼即可了解。

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

    bool queue_enqueue(queue_t *self, int data)
    {
        if (!queue_expand(self)) {
            return false;
        }
        
        if (self->size > 0) {
            self->tail = (self->tail + 1) % self->capacity;
        }
    
        self->elements[self->tail] = data;
        self->size += 1;
        
        return true;
    }

    要擴展佇列時,會先建立一個新的陣列,再將原陣列的資料逐一拷貝到新陣列上:

    擴展佇列陣列容量

    新的容量是原陣列大小的兩倍。

    以下是 Expand 部分的虛擬碼:

    Q is a queue.
    
    sub Expand(Q): void
        if Q.size < Q.capacity then
            return
        end if
        
        old_arr <- Q.elements
        Q.capacity <- Q.size * 2
        new_arr <- allocate a zero-based array with size == Q.capacity
        
        sz <- 0
        i <- Q.head
        j <- Q.head
        while sz < Q.size do
            new_arr[i] <- old_arr[j]
            
            i <- (i + 1) % Q.capacity
            j <- (j + 1) % Q.size
            sz += 1
        end while
        
        Q.elements <- new_arr
        Q.tail <- (Q.head + Q.size - 1) % Q.capacity
        delete old_arr
    

    我們同樣用環狀陣列的手法拷貝元素,要注意 ij 的平移距離不同,因 old_arrnew_arr 的大小不同。

    將上述虛擬碼換成等效的 C 語言實作如下:

    static bool queue_expand(queue_t *self)
    {
        if (self->size < self->capacity) {
            return true;
        }
    
        self->capacity <<= 1;
        int *old_arr = self->elements;
        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;
        self->tail = (self->head + self->size - 1) % self->capacity;
        free(old_arr);
        
        return true;
    }

    將資料移出佇列

    要將資料移出佇列時,先移動 head

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

    其實這樣就完成了。日後新增節點時會自動覆蓋掉該位置的資料:

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

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

    Q is a queue.
    
    sub Dequeue(Q): data
        assert(not IsEmpty(Q))
        
        popped <- Q.elements[Q.head]
        Q.head <- (Q.head + 1) % Q.capacity
        Q.size -= 1
        
        return popped
    

    由於推出資料時,head 是向後推移,故其值為加 1 而非減 1,同樣要用環狀陣列的手法平移。

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

    int queue_dequeue(queue_t *self)
    {
        assert(!queue_is_empty(self));
        
        int popped = self->elements[self->head];
        self->head = (self->head + 1) % self->capacity;
        self->size -= 1;
        
        return popped;
    }

    在演算法上的效率

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

    • IsEmpty: O(1)
    • Peek: O(1)
    • Enqueue: amortized O(1)
    • Dequeue: O(1)

    如同先前堆疊的例子,在執行 Enquene 時若陣列有擴張,其效率為 O(n),但以攤平分析法 (amortized analysis) 來分析可知其效率為 O(1)

    【贊助商連結】
    【贊助商連結】
    【分類瀏覽】