Queue: 以Array實作Queue

Posted by Chiu CC on 4 29, 2016


先備知識與注意事項

本篇文章將接續Queue: Intro(簡介)，並以Linked list實作，介紹以Array實作Queue的方法。

關於Queue對資料的基本處理方法如Push()、Pop()等等，請參考Intro篇的介紹。

目錄


浪費記憶體空間的Array實作：Sequential Queue

如圖一，以Array實作Queue(隊伍)時，需定義兩個變數來記住Array的index：

  • 以front記住隊伍的開頭index；
  • 以back記住隊伍的尾端index；

進行以下操作：

  • Push：若要新增資料，按照Array的index順序：\(0、1、2...\)，從Queue的back新增資料。
  • Pop：若要刪除資料，按照Array的index順序：\(0、1、2...\)，從Queue的front刪除資料。
    • Pop並沒有真正把Array的記憶體位置釋放，只是調整front，使得Queue「看起來」有刪除資料。

cc

圖一。

以上介紹的方法會有記憶體空間浪費的問題。
由於圖一的Push是不斷往Queue的back新增資料，因此Array的前兩個位置一旦被「想像地Pop」後，會一直閒置到整個Array的記憶體被釋放為止，無法有效利用。

下一小節將提出另一種以Array實作Queue的方法，將能夠有效利用Array中曾經被Pop過的記憶體位置。

cc

圖二。

另外，圖二的Array顯然已經填滿，若要在此Queue繼續增加資料，就需要重新配置一個容量更大的Array，方法如圖三，將資料複製到新的Array上，並且調整front與back。

cc

圖三。

完整的程式範例如下：

// C++ code

#include <iostream>
using std::cout;

class QueueArraySequential{
private:
    int capacity, front, back;
    int *queue;
    void DoubleCapacity();
public:
    QueueArraySequential():capacity(5),front(-1),back(-1){
        queue = new int[capacity];
    };
    void Push(int x);
    void Pop();
    bool IsEmpty();
    bool IsFull();
    int getFront();
    int getBack();
    int getSize();
    int getCapacity();    // 驗證用, 可有可無
};

void QueueArraySequential::DoubleCapacity(){

    capacity *= 2;
    int *newQueue = new int[capacity];

    int j = -1;
    for (int i = front+1; i <= back; i++) {
        j++;
        newQueue[j] = queue[i];
    }
    front = -1;       // 新的array從0開始, 把舊的array"整段平移", front跟back要更新
    back = j;
    delete [] queue;
    queue = newQueue;
}
void QueueArraySequential::Push(int x){

    if (IsFull()) {
        DoubleCapacity();
    }
    queue[++back] = x;
}
void QueueArraySequential::Pop(){

    if (IsEmpty()) {
        std::cout << "Queue is empty.\n";
        return;
    }
    front++;        
}
bool QueueArraySequential::IsFull(){

    return (back + 1 == capacity);
}
bool QueueArraySequential::IsEmpty(){

    return (front  == back);
}
int QueueArraySequential::getFront(){

    if (IsEmpty()) {
        std::cout << "Queue is empty.\n";
        return -1;
    }

    return queue[front+1];
}
int QueueArraySequential::getBack(){

    if (IsEmpty()) {
        std::cout << "Queue is empty.\n";
        return -1;
    }

    return queue[back];
}
int QueueArraySequential::getSize(){

    return (back - front);
}
int QueueArraySequential::getCapacity(){

    return capacity;
}

void printSequentialQueue (QueueArraySequential queue){
    cout << "front: " << queue.getFront() << "    back: " << queue.getBack() << "\n"
    << "capacity: " << queue.getCapacity() << "  number of elements: " << queue.getSize() << "\n\n";
}
int main(){

    QueueArraySequential q;
    if (q.IsEmpty()) {
        cout << "Queue is empty.\n\n";
    }
    q.Push(24);
    cout << "After push 24: \n";
    printSequentialQueue(q);
    q.Push(8);
    q.Push(23);
    cout << "After push 8, 23: \n";
    printSequentialQueue(q);
    q.Pop();
    cout << "After pop 24: \n";
    printSequentialQueue(q);
    q.Push(13);
    cout << "After push 13: \n";
    printSequentialQueue(q);
    q.Pop();
    cout << "After pop 8: \n";
    printSequentialQueue(q);
    q.Push(35);
    cout << "After push 35: \n";
    printSequentialQueue(q);
    q.Push(9);
    cout << "After push 9: \n";
    printSequentialQueue(q);

    return 0;
}

output:

Queue is empty.

After push 24: 
front: 24    back: 24
capacity: 5  number of elements: 1

After push 8, 23: 
front: 24    back: 23
capacity: 5  number of elements: 3

After pop 24: 
front: 8    back: 23
capacity: 5  number of elements: 2

After push 13: 
front: 8    back: 13
capacity: 5  number of elements: 3

After pop 8: 
front: 23    back: 13
capacity: 5  number of elements: 2

After push 35: 
front: 23    back: 35
capacity: 5  number of elements: 3

After push 9: 
front: 23    back: 9
capacity: 10  number of elements: 4

在main()的測試中，最重要的是執行Push(9)的前後。

在Push(9)之前，Array的狀況如圖四(a)：

  • 此時，Queue其實只有\(3\)筆資料，理論上，具有大小為\(5\)的Array應該要能夠再新增一筆資料。
  • 但是因為上述的Push()與Pop()，Array的前兩個記憶體位置無法重複利用。

cc

圖四(a)。

因此，若要Push(9)，就需要重新配置容量更大的Array，才能在Queue中新增\(9\)，見圖四(b)：

  • 此時，Queue其實只有\(4\)筆資料，但是使用了capacity為\(10\)的Array。
    • 這裡的capacity更新成\(10\)是因為程式範例中DoubleCapacity()的寫法。
    • 根據不同「重新配置Array」的寫法，更新後的capacity大小可能會有所不同。

cc

圖四(b)。

根據以上說明，第一種方法不只是記憶體空間的浪費，還有「重新配置Array」的運算成本浪費。

接下來便介紹第二種以Array實作Queue的方法，能夠較為有效地利用Array的記憶體位置。


節省記憶體空間的Array實作：Circular Queue

第二種方法做出來的Queue又稱為Circular Queue，環狀(circular)的意思就是能夠「繞回Array的前端」，重複利用Array的記憶體空間，見圖五：

cc

圖五。

比較圖一的Sequential Queue與圖五的Circular Queue之差異：

  • Sequential Queue：

    • front與back之初始值為\(-1\)。
    • 一但被Pop後的記憶體空間將閒置到Queue的物件(object)被釋放。

  • Circular Queue：

    • front與back之初始值為\(0\)，因此會犧牲Array中的其中一個記憶體位置。
    • 被Pop後的記憶體空間將會重複使用，將會用上餘數(mod)來計算index。

完整的程式範例如下：

// C++ code

#include <iostream>
using std::cout;

class QueueArrayCircular{
private:
    int capacity, front, back;
    int *queue;
    void DoubleCapacity();
public:
    QueueArrayCircular():capacity(5),front(0),back(0){     // 從0開始, 第一個位置放掉
        queue = new int[capacity];
    }
    void Push(int x);
    void Pop();
    bool IsEmpty();
    bool IsFull();
    int getFront();
    int getBack();
    int getSize();
    int getCapacity();    // 驗證用, 可有可無
};

void QueueArrayCircular::DoubleCapacity(){

    int *newQueue = new int[capacity*2];

    int j = front, size = getSize();
    for (int i = 1; i <= size; i++) {
        newQueue[i] = queue[++j % capacity];    // j 要先加一, 因為 front 沒有東西
    }

    back = getSize();   // 要在更改 capacity 之前抓住 back
    front = 0;          // 改變 front 要在 getSize() 之後
    capacity *= 2;

    delete [] queue;
    queue = newQueue;
}
void QueueArrayCircular::Push(int x){

    if (IsFull()) {
        DoubleCapacity();
    }

    back = (back + 1)%capacity;
    queue[back] = x;
}
void QueueArrayCircular::Pop(){

    if (IsEmpty()) {
        std::cout << "Queue is empty.\n";
        return;
    }

    front = (front + 1)%capacity;
}
bool QueueArrayCircular::IsEmpty(){

    return (front == back);
}
bool QueueArrayCircular::IsFull(){

    return ((back + 1)%capacity == front);
}
int QueueArrayCircular::getFront(){

    if (IsEmpty()) {
        std::cout << "Queue is empty.\n";
        return -1;
    }
    return queue[(front + 1)%capacity];
}
int QueueArrayCircular::getBack(){

    if (IsEmpty()) {
        std::cout << "Queue is empty.\n";
        return -1;
    }

    return queue[back];
}
int QueueArrayCircular::getSize(){

    int size;
    if (front < back) {
        size = back - front;
    }
    else {
        size = capacity - (front - back);
    }

    return size;
}
int QueueArrayCircular::getCapacity(){

    return capacity;
}

void printCircularQueue (QueueArrayCircular queue){
    cout << "front: " << queue.getFront() << "    back: " << queue.getBack() << "\n"
    << "capacity: " << queue.getCapacity() << "  number of elements: " << queue.getSize() << "\n\n";
}

int main(){

    QueueArrayCircular q;
    if (q.IsEmpty()) {
        cout << "Queue is empty.\n\n";
    }
    q.Push(24);
    cout << "After push 24:\n";
    printCircularQueue(q);
    q.Push(8);
    q.Push(23);
    cout << "After push 8, 23:\n";
    printCircularQueue(q);
    q.Pop();
    cout << "After pop 24:\n";
    printCircularQueue(q);
    q.Push(13);
    cout << "After push 13:\n";
    printCircularQueue(q);
    q.Pop();
    cout << "After pop 8:\n";
    printCircularQueue(q);
    q.Push(35);
    cout << "After push 35:\n";
    printCircularQueue(q);
    q.Push(9);
    cout << "After push 9:\n";
    printCircularQueue(q);
    q.Push(64);
    cout << "After push 64:\n";
    printCircularQueue(q);
    return 0;
}

output:

Queue is empty.

After push 24:
front: 24    back: 24
capacity: 5  number of elements: 1

After push 8, 23:
front: 24    back: 23
capacity: 5  number of elements: 3

After pop 24:
front: 8    back: 23
capacity: 5  number of elements: 2

After push 13:
front: 8    back: 13
capacity: 5  number of elements: 3

After pop 8:
front: 23    back: 13
capacity: 5  number of elements: 2

After push 35:
front: 23    back: 35
capacity: 5  number of elements: 3

After push 9:
front: 23    back: 9
capacity: 5  number of elements: 4

After push 64:
front: 23    back: 64
capacity: 10  number of elements: 5

在main()中的測試結果可以看出，Circular Queue確實有效地利用了Array的記憶體空間，與Sequential Queue比較，在Push(9)時，並沒有呼叫DoubleCapacity()，因為Circular Queue的Push()會將資料新增至Array的開頭，如圖六：

cc

圖六。

而接續圖六的狀態後，再繼續Push(10)就會呼叫DoubleCapacity()，如圖七，要注意的是必須按照front到back的順序複製資料，並且更新front與back所代表的index：

cc

圖七。


以上是以Array實作Sequential Queue與Circular Queue的介紹。


參考資料：

致謝

感謝網友enrngnhn來信指認程式碼的邏輯錯誤。


Queue系列文章

Queue: Intro(簡介)，並以Linked list實作
Queue: 以Array實作Queue

回到目錄：

目錄：演算法與資料結構


tags: C++, Queue, Array,