[資料結構] 使用 C 語言:以陣列 (Array) 實做雙向佇列 (Deque)

【分享本文】
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

    雙向佇列的抽象資料結構

    在本文中,我們仍然實作雙向佇列,但內部改以陣列來實作。

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

    Q is a deque.
    
    sub IsEmpty(Q): bool
    (Optional) IsFull(Q): bool
    (Optional) Size(Q): sz
    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
    

    基本上抽象資料結構是相同的,故不重覆說明。

    雙向佇列的類別宣告

    以陣列為基礎的雙向佇列的圖示如下:

    以陣列實作的雙向佇列

    以陣列為基礎的類別宣告的虛擬碼如下:

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

    將上述宣告轉成 C 語言實作如下:

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

    雙向佇列的建構函式

    以 C 語言實作建構函式如下:

    deque_t * deque_new(void)
    {
        deque_t *dq = malloc(sizeof(deque_t));
        if (!dq)
            return dq;
        
        dq->size = 0;
        dq->capacity = 2;
        dq->head = 0;
        dq->tail = 0;
        
        dq->elements = malloc(dq->capacity * sizeof(int));
        if (!(dq->elements)) {
            free(dq);
            dq = NULL;
            return dq;
        }
        
        return dq;
    }

    一開始的 capacity 只要大於等於 2 即可;一般使用下可設 16,此處故意設 2 是為了看佇列擴張時是否會引發錯誤。

    雙向佇列的解構函式

    以下是 C 語言的雙向佇列解構函式:

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

    先釋放內部陣列後,再釋放佇列物件本身。

    確認雙向佇列是否為空

    IsEmpty 的虛擬碼如下:

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

    在我們的實作中,會儲存佇列大小的資訊,要檢查佇列是否為空時檢查此屬性即可。以 C 語言實作如下:

    bool deque_is_empty(const deque_t *self)
    {
        assert(self);
        
        return self->size <= 0;
    }

    檢視雙向佇列頭端的資料

    PeekFront 的虛擬碼如下:

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

    我們的 head 以數字做為索引值 (index value),用來取代指標。以 C 語言實作如下:

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

    檢視雙向佇列尾端的資料

    PeekRear 的虛擬碼如下:

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

    PeekFront 類似,以數字做為索引來取代指標。以 C 語言實作如下:

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

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

    要將資料推入雙向佇列尾端前,要先移動 tail,如下圖:

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

    接著將資料寫入即可:

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

    Push (或 PushRear) 的虛擬碼如下:

    Q is a deque.
    
    sub Push(Q, data): void
        Expand(Q)
        
        if Q.size > 0 then
            Q.tail <- (Q.tail + 1) % Q.capacity
        endif
        
        Q.elements[Q.tail] <- data
        Q.size++
    

    一開始要視需求擴張雙向佇列,我們會在下文介紹 Expand() 函式的實作。

    要注意佇列為空和非空時的處理方法不同,佇列為空時,索引值不會跳動,但佇列大小會加 1,之後則索引值和佇列大小皆會加 1。以 C 語言實作如下:

    static bool deque_expand(deque_t *self);
    
    bool deque_push(deque_t *self, int data)
    {
        if (!deque_expand(self)) {
            return false;
        }
        
        if (!deque_is_empty(self)) {
            self->tail = (self->tail + 1) % self->capacity;
        }
    
        self->elements[self->tail] = data;
        self->size += 1;
    
        return true;
    }

    擴張雙向佇列內部的陣列的原理是建立一個新的陣列後,將資料逐一拷貝到新的陣列上。如下圖:

    擴張以陣列為基礎的雙向佇列

    一般會把新的陣列的最大容量設為原本陣列的大小的兩倍。

    我們把 Expand 部分的虛擬碼拉出來看:

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

    重點在佇列擴張時,新的內部陣列的大小是舊的內部陣列的兩倍大,處理索引值的分母相異。以 C 語言實作如下:

    static bool deque_expand(deque_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。如下圖:

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

    之後再將資料寫入即可。如下圖:

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

    以下是 Unshift (或 PushFront) 的虛擬碼:

    Q is a deque.
    
    sub Unshift(Q, data): void
        Expand(Q)
        
        if Q.size == 0 then
            Q.elements[Q.head] <- data
            Q.size++
            return
        end if
        
        Q.head = Q.head == 0 ? Q.capacity - 1 : Q.head - 1
    
        Q.elements[Q.head] <- data
        Q.size++
    

    雖然佇列大小變大,但頭端是往回走,故要減 1 而非加 1,同樣要注意索引值為 0 時的處理方法。以下是 C 語言實作:

    bool deque_unshift(deque_t *self, int data)
    {
        if (!deque_expand(self)) {
            return false;
        }
    
        if (deque_is_empty(self)) {
            self->elements[self->head] = data;
            self->size += 1;
            return true;
        }
    
        self->head = self->head == 0 ? self->capacity - 1 : self->head - 1;
        self->elements[self->head] = data;
        self->size += 1;
    
        return true;
    }

    將資料從雙向佇列尾端推出

    將尾端資料拷貝出來後,移動 tail。如下圖:

    將資料移出雙向佇列的尾端 (步驟一)

    其實在移動完 tail 後,整個動作就算完成了。之後在寫入新資料時會自動覆蓋掉原本的資料。如下圖:

    將資料移出雙向佇列的尾端 (步驟二)

    以下是 Pop (或 PopRear) 的虛擬碼:

    Q is a deque.
    
    sub Pop(Q): data
        assert(not IsEmpty(Q))
        
        popped <- Q.elements[Q.tail]
        Q.tail = Q.tail == 0 ? Q.capacity - 1 : Q.tail - 1
        
        return popped
    

    由於索引值不能為負,注意當索引值為 0 時的處理方式。以下是等效的 C 語言實作:

    int deque_pop(deque_t *self)
    {
        assert(!deque_is_empty(self));
        
        int popped = self->elements[self->tail];
        self->tail = self->tail == 0 ? self->capacity - 1 : self->tail - 1;
        self->size -= 1;
    
        return popped;
    }

    將資料從雙向佇列頭端推出

    將頭端資料拷貝出來後,移動 head。如下圖:

    將資料移出雙向佇列的頭端 (步驟一)

    其實在移動完 head 後,整個動作就算完成了。之後在寫入新資料時會自動覆蓋掉原本的資料。如下圖:

    將資料移出雙向佇列的頭端 (步驟二)

    以下是 Shift (或 PopFront) 的虛擬碼:

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

    雖然佇列大小變小,但索引是往後推,故索引值是加 1 而非減 1。以 C 語言實作如下:

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

    在演算法上的效率

    此範例程式在演算法上的效率如下:

    • IsEmpty(Q)O(1)
    • PeekFront(Q)O(1)
    • PeekRear(Q)O(1)
    • Push(Q, data):amortized O(1)
    • Unshift(Q, data):amortized O(1)
    • Pop(Q)O(1)
    • Shift(Q)O(1)

    佇列在擴張時,其效率為 O(n),若未擴張,其效率為 O(1);經攤平分析法 (amortized analysis) 可知其攤平後的效率為 O(1)

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
    【追蹤新文章】
    Facebook Twitter Plurk
    標籤: DATA STRUCTURES