本文已經過時, 最新文章請點擊 : 《【資料結構 – 重構】佇列與迴圈佇列》

《資料結構 : 佇列》中, 曾經提到普通的陣列佇列中的出隊算法太麻煩, 需要一個一個元素操作, 那麼為了避免這樣複雜的算法, 於是就有迴圈佇列 (環狀佇列)

迴圈佇列中的循環的意義與循環線性表的意義是不同的, 這裏的循環著要是指我們設定的佇列指標 rear 和 front 循環. 也就是不讓他們超出陣列的位址範圍, 同時避免出現佇列假空或者假滿的現象

我們之前提出的普通陣列佇列也是一種陣列佇列的解決方案, 只是 front 不動的解決方案的算法太麻煩了, 為了避免將時間浪費在沒有必要的算法上, 所以我們提出迴圈佇列這樣的優化

首先我們來討論為什麼會出現佇列的假空現象或者假滿現象 :

如果我們假設佇列指標 front 和 rear 都可以移動, 那麼一開始 front == nullptr 這樣的條件就要更改, 我們要讓 front 和 rear 同時指向陣列的首個元素. 那麼此時, front == rear 這個條件就成為佇列判空的條件. 但是當我們不斷地對佇列進行入隊, rear 始終都會移動到陣列的位址外. 那麼此時, 我們應當將 rear 設定回到陣列的首個位址, 於是又有了 front == rear, 佇列會被判空. 雖然判斷佇列為空, 其實佇列是滿的

現在, 假設有一個指標陣列 : arr, 陣列最大維度 : maxSize. 我們使用 rear == arr + maxSize - 1 判斷佇列是否為滿. 我們仍然不斷進行佇列入隊使得佇列滿, 此時 rear == arr + maxSize - 1 成立. 我們再讓佇列出隊, 不管出多少, rear == arr + maxSize - 1 條件仍然是成立的, 因為 rear 指標根本就沒有移動. 此時我們不能再進行佇列入隊的操作, 佇列會被判斷為滿, 但是實際上, 佇列仍然有空位

為了避免出現這種情況, 同時為了不讓佇列出隊的算法如此麻煩, 於是有兩種解決方案, 這兩種解決方案都可以構成迴圈佇列 :

  • 犧牲陣列中一個位置, 當 front + 1 == rear 條件成立的時候, 就禁止佇列入隊. 這樣 front 永遠都不會追上 rear. 這樣佇列位置滿了的時候, 就不會出現 front == rear 這個情況, 這個情況只在佇列空的時候出現. 此時, 判斷佇列是否滿的條件為 : (rear - front + maxSize) % maxSize == maxSize - 1, 其中 rear 和 front 都為 C++ 中的指標
  • 在類別中放置一個標誌量 tag, 最好是 bool 型態. 以 tag 的狀態判斷佇列是否可以繼續進行入隊的操作. 這種方法不會損失陣列中的元素. 此時, 佇列判斷空或者滿的前提條件是 front == rear, 並且還要看標誌量 tag 的狀態. 每當佇列入隊, 檢測 front == rear, 若成立, 則改變 tag 狀態, 表示佇列已滿; 每當佇列出隊, 也要檢測 front == rear, 若成立, 也要改變 tag 狀態, 表示佇列空

在設定 front 與 rear 的時候, 我們應當注意它們是否還在陣列位址範圍之內.

我們假設現在有指標陣列 arr, 陣列指標 front 與 rear, 陣列長度標誌 maxSize

我們以 front 為例子, 一旦 front 發生改動, 就執行

front = arr + (front - arr) % maxSize;

關於佇列的基本特性, 可以移步《資料結構 : 佇列》. 並且本篇的類別是繼承上篇的 Queue 類別


下面是本人寫的原始碼

如若有錯誤存在, 可以聯絡我或者直接添加評論. 關於原始碼的註解, 已經給的比較全面, 還有不明白的可以直接評論, 對於註解的建議也可以提出. 直接讀原始碼的函式名稱或者變數名稱可以直接了解作用

CircularQueue_Sacrifice.hpp :

#ifndef CIRCULARQUEUE_CIRCULARQUEUE_SACRIFICE_HPP
#define CIRCULARQUEUE_CIRCULARQUEUE_SACRIFICE_HPP

#include "SequentialQueue.hpp"

using namespace SequentialQueue;

class Queue_Sacrifice : public Queue {
private :
    bool isFull();
    bool isEmpty();
public :
    Queue_Sacrifice(unsigned maxSize);
    long long int getFront();
    void enter(int data);
    void out();
    void clearQueue();
    void showQueue();
};


#endif //CIRCULARQUEUE_CIRCULARQUEUE_SACRIFICE_HPP

CircularQueue_Sacrifice.cpp :

#include "CircularQueue_Sacrifice.hpp"

using namespace SequentialQueue;

Queue_Sacrifice::Queue_Sacrifice(unsigned maxSize) {
    this->maxSize = maxSize;
    this->arr = new int[this->maxSize];
    this->front = this->arr;
    this->rear = this->arr;
}
bool Queue_Sacrifice::isEmpty() {
    if(this->front == this->rear) {
        return true;
    }
    return false;
}
bool Queue_Sacrifice::isFull() {
    if((this->rear - this->front + this->maxSize) % this->maxSize == this->maxSize - 1) {
        return true;
    }
    return false;
}
long long int Queue_Sacrifice::getFront() {
    if(isEmpty()) {
        return INT64_MIN;
    }
    return (long long int)*this->front;
}
void Queue_Sacrifice::enter(int data) {
    if(isFull()) {
        cout << "The queue is full!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    *this->rear = data;
    this->rear++;
    this->rear = this->arr + (this->rear - this->arr) % this->maxSize;      //If the pointer exceeds the array, set pointer back to array.
}
void Queue_Sacrifice::out() {
    if(isEmpty()) {
        cout << "The queue is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    cout << "The element : " << *this->front << " has been out!" << endl;
    this->front++;
    this->front = this->arr + (this->front - this->arr) % this->maxSize;        //If the pointer exceeds the array, set pointer back to array.
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Queue_Sacrifice::clearQueue() {
    delete arr;
    arr = new int[this->maxSize];
    this->front = arr;
    this->rear = arr;
}
void Queue_Sacrifice::showQueue() {
    if(isEmpty()) {
        return;
    }
    int *p = this->front;       //iterator
    int count = 0;      //Size of queue.
    /* Count the size of queue. */
    while(p != this->rear) {
        count++;
        p++;
        p = this->arr + (p - this->arr) % this->maxSize;
    }
    /* Print index : */
    cout << "Index : \t";
    for(int i = 1; i <= count; i++) {
        cout << i << "\t";
    }
    cout << endl << "Element : \t";
    p = this->front;        //Reset iterator.
    /* Print element : */
    while(p != this->rear) {
        cout << *p << "\t";
        p++;
        p = this->arr + (p - this->arr) % this->maxSize;
    }
    cout << endl;
    p = nullptr;
    delete p;
}

CircularQueue_Tag.hpp :

#ifndef CIRCULARQUEUE_CIRCULARQUEUE_TAG_HPP
#define CIRCULARQUEUE_CIRCULARQUEUE_TAG_HPP

#include "SequentialQueue.hpp"

using namespace SequentialQueue;

class Queue_Tag : public Queue {
private :
    bool tag;       //If rear == front and tag == true means the queue is empty, or the queue is full.
    bool isFull();
    bool isEmpty();
public :
    Queue_Tag(unsigned maxSize);
    long long int getFront();
    void enter(int data);
    void out();
    void clearQueue();
    void showQueue();
};


#endif //CIRCULARQUEUE_CIRCULARQUEUE_TAG_HPP

CircularQueue_Tag.cpp :

#include "CircularQueue_Tag.hpp"

using namespace SequentialQueue;

Queue_Tag::Queue_Tag(unsigned maxSize) {
    this->maxSize = maxSize;
    this->arr = new int[this->maxSize];
    this->front = this->rear = this->arr;
    this->tag = true;
}
bool Queue_Tag::isEmpty() {
    if(this->rear == this->front && this->tag) {
        return true;
    }
    return false;
}
bool Queue_Tag::isFull() {
    if(this->rear == this->front && !this->tag) {
        return true;
    }
    return false;
}
long long int Queue_Tag::getFront() {
    if(isEmpty()) {
        return INT64_MIN;
    }
    return (long long int)*this->front;
}
void Queue_Tag::enter(int data) {
    if(isFull()) {
        cout << "The queue is full!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    *this->rear = data;
    this->rear++;
    this->rear = this->arr + (this->rear - this->arr) % this->maxSize;      //If the pointer exceeds the array, set pointer back to array.
    if(this->rear == this->front) {
        this->tag = false;
    }
}
void Queue_Tag::out() {
    if(isEmpty()) {
        cout << "The queue is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    cout << "The element : " << *this->front << " has been out!" << endl;
    this->front++;
    this->front = this->arr + (this->front - this->arr) % this->maxSize;        //If the pointer exceeds the array, set pointer back to array.
    if(this->rear == this->front) {
        this->tag = true;
    }
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Queue_Tag::clearQueue() {
    this->front = nullptr;
    this->rear = nullptr;
    delete this->arr;
    this->arr = new int[this->maxSize];
    this->front = this->arr;
    this->rear = this->arr;
    this->tag = true;
}
void Queue_Tag::showQueue() {
    if(isEmpty()) {
        return;
    }
    int *p = this->front;       //iterator
    if(!isFull()) {
        int count = 0;      //Size of queue
        /* Count the size of queue */
        while(p != this->rear) {
            count++;
            p++;
            p = this->arr + (p - this->arr) % this->maxSize;
        }
        /* Print index : */
        cout << "Index : \t";
        for(int i = 1; i <= count; i++) {
            cout << i << "\t";
        }
        cout << endl << "Element : \t";
        p = this->front;
        /* Print element : */
        while(p != this->rear) {
            cout << *p << "\t";
            p++;
            p = this->arr + (p - this->arr) % this->maxSize;        //If the pointer exceeds the array, set pointer back to array.
        }
        cout << endl;
    }else {
        /* Print index : */
        cout << "Index : \t";
        for(int i = 1; i <= this->maxSize; i++) {
            cout << i << "\t";
        }
        cout << endl << "Element : \t" << *p << "\t";
        p++;
        p = this->arr + (p - this->arr) % this->maxSize;        //If the pointer exceeds the array, set pointer back to array.
        /* Print element : */
        while(p != this->rear) {
            cout << *p << "\t";
            p++;
            p = this->arr + (p - this->arr) % this->maxSize;        //If the pointer exceeds the array, set pointer back to array.
        }
        cout << endl;
    }
    p = nullptr;
    delete p;
}

main.cpp :

#include "CircularQueue_Sacrifice.hpp"
#include "CircularQueue_Tag.hpp"

using namespace SequentialQueue;
using std::string;

void menu();

int main(int argc, char *argv[]) {
    int choice;
    unsigned maxSize;
    cout << "Please enter the max size of queue : ";
    cin >> maxSize;
    Queue *queue;
    system("clear");
    cout << "Type of queue : " << endl;
    cout << "--------------------------------------------" << endl;
    cout << "1. Sacrifice Queue (this queue will sacrifice one position)." << endl;
    cout << "2. Tag Queue." << endl;
    cout << "--------------------------------------------" << endl;
    cout << "You should enter the full name of queue. If you enter wrongly, the system will choose Tag Queue automatically!" << endl;
    cout << "Please choose the type of queue : ";
    cin >> choice;
    if(choice == 1) {
        queue = new Queue_Sacrifice(maxSize);
    }else {
        queue = new Queue_Tag(maxSize);
    }
    long long int front;        //The front element
    int data;       //The data user want to enter to the queue
    /* Test the queue automatically : To see whether the abnormally number will show */
    /*int randomNumber;
    srand((unsigned)time(nullptr));
    for(int i = 0; i < 10000; i++) {
        randomNumber = rand() % 2 + 1;
        data = rand() % 100;
        if(randomNumber == 1) {
            queue->enter(data);
            queue->showQueue();
        }else {
            queue->out();
            queue->showQueue();
        }
    }*/
    do {
        system("clear");
        queue->showQueue();
        menu();
        cin >> choice;
        switch(choice) {
            case 1 :
                front = queue->getFront();
                if(front == INT64_MIN) {
                    cout << "The queue is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The front element : " << front << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 2 :
                cout << "Please enter the element you want to enter : ";
                cin >> data;
                queue->enter(data);
                break;
            case 3 :
                queue->out();
                break;
            case 4 :
                queue->clearQueue();
                break;
            case 5 :
                delete queue;
                exit(0);
            default :
                break;
        }
    }while(choice != 5);
}
void menu() {
    cout << "--------------------------------------------" << endl;
    cout << "1. Get the front element." << endl;
    cout << "2. Enter." << endl;
    cout << "3. Out." << endl;
    cout << "4. Clear the queue." << endl;
    cout << "5. Exit." << endl;
    cout << "--------------------------------------------" << endl;
    cout << "Please enter your choice : ";
}