資料結構 : 佇列

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

佇列與堆疊形式上對應, 也是一種限定線性表, 它只允許在一端輸入, 另一端刪除

所以佇列的基本特性 :

First In First Out (FIFO)

允許插入的一端稱為後端 (rear), 允許刪除的一端為前端 (front)

在我所寫的佇列中, 我設定了四個元素 :

front : 前端
rear : 後端
maxSize : 佇列最大長度
usedSize : 佇列已用長度

1. 空佇列

因為佇列為空, 所以前端指標不應該指向任何位址, 即有 front = nullptr. 另外, 我們設定 rear 指標永遠指向後一個記憶體位址內數據為空的位址

用一張 SVG 圖像表示 :

2. 佇列入隊

因為每一次都只能從後端入隊, 即每一次都是從 rear 這裏入隊, 所以輸入數據到 *rear 即可. 同時, rear 要向後移動一個位置, 因為 rear 永遠只能指向最後一個元素的後一個位址

當 front == nullptr 的時候, 我們有必要讓 front 指向陣列, 並且 front 永遠指向陣列的第一個元素

用一張 SVG 圖像表示 :

3. 佇列出隊

佇列只能從前端刪除元素, 每次都只要刪除 front 指標對應的數據即可. 但是要保證不能出現佇列假空現象 (陣列中實際沒有任何元素, 但是 front 指標已經超過了陣列指標範圍), 所以我們需要保證 front 要麼為空指標, 要麼就永遠指向陣列的首個元素對應的記憶體位址. 同時, 每一次出隊之後, rear 指標都要向前移動

出隊的時候, 就要麻煩一點, 要將第一個元素後面的全部元素都在陣列的範圍內往前移動一個位置

(為了避免這樣的算法, 後面就會介紹循環佇列, 大大簡化了佇列出隊時的算法)

通過觀察陣列佇列, 我們可以發現, 我們可以通過如下表達式計算出佇列中目前已有的元素個數

QueueSize = (rear - front + maxSize) % maxSize

其中, rear 與 front 都是 C++ 指標

由於佇列的程式碼較為簡單, 通過直接看代碼可以快速理解, 所以註解會比較少

循環佇列的程式碼將會繼承本篇文章中的 SequentialQueue.hpp 中的 Queue 類別

下面是本人寫的原始碼

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

SequentialQueue.hpp :

#ifndef SEQUENTIALQUEUE_SEQUENTIALQUEUE_HPP
#define SEQUENTIALQUEUE_SEQUENTIALQUEUE_HPP

#include <iostream>
#include <cstdlib>

namespace SequentialQueue {
    using std::cin;
    using std::cout;
    using std::endl;
    class Queue {
    private :
        unsigned usedSize;
        bool isEmpty();
        bool isFull();
    protected :
        int *arr;
        unsigned maxSize;
        int *front;
        int *rear;
        Queue();        //Set function to protected to avoid anyone who is fucking stupid calling it.
    public :
        Queue(unsigned maxSize);
        ~Queue();
        long long int getFront();
        virtual void enter(int data);
        virtual void out();
        virtual void clearQueue();
        virtual void showQueue();
    };
}

SequentialQueue.cpp :

#include "SequentialQueue.hpp"

using namespace SequentialQueue;

Queue::Queue() {

}
Queue::Queue(unsigned maxSize) {
    this->maxSize = maxSize;
    this->usedSize = 0;
    this->arr = new int[maxSize];
    this->rear = arr;
    this->front = nullptr;
}
Queue::~Queue() {
    this->rear = nullptr;
    this->front = nullptr;
    delete []this->arr;
    delete this->rear;
    delete this->front;
}
bool Queue::isEmpty() {
    if(!this->usedSize) {
        return true;
    }
    return false;
}
bool Queue::isFull() {
    if(this->usedSize == this->maxSize) {
        return true;
    }
    return false;
}
long long int Queue::getFront() {
    if(isEmpty()) {
        return INT64_MIN;
    }
    return (long long int)*this->front;
}
void Queue::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++;
    if(!this->front) {
        this->front = arr;
    }
    this->usedSize++;
}
void Queue::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;
    /* Let elements go head one position. */
    for(int *i = this->front; i < this->rear; i++) {
        *i = *i + 1;
    }
    this->rear--;
    this->usedSize--;
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Queue::clearQueue() {
    this->usedSize = 0;
    this->front = nullptr;
    this->rear = this->arr;
}
void Queue::showQueue() {
    if(isEmpty()) {
        return;
    }
    /* Print index : */
    cout << "Index : \t";
    for(int i = 1; i <= this->usedSize; i++) {
        cout << i << "\t";
    }
    /* Print element : */
    cout << endl << "Element : \t";
    for(int *i = this->front; i < this->rear; i++) {
        cout << *i << "\t";
    }
    cout << endl;
}

main.cpp :

#include "SequentialQueue.hpp"

using namespace SequentialQueue;

void menu();

int main(int argc, char *argv[]) {
    Queue *queue;
    unsigned maxSize;
    cout << "Please enter the max size of queue : ";
    cin >> maxSize;
    queue = new Queue(maxSize);
    int choice;
    long long int frontData;
    int data;
    /* Test module : To test whether the queue is normal. */
    /*srand((unsigned)time(nullptr));
    while(true) {
        choice = rand() % 3 + 1;
        switch(choice) {
            case 1 :
                data = rand() % 10 + 1;
                queue->enter(data);
                break;
            case 2 :
                queue->out();
                break;
            case 3 :
                queue->clearQueue();
                break;
        }
        queue->showQueue();
    }*/
    do {
        system("clear");
        queue->showQueue();
        menu();
        cin >> choice;
        switch(choice) {
            case 1 :
                frontData = queue->getFront();
                if(frontData == INT64_MIN) {
                    cout << "The queue is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The front element : " << frontData << 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 : ";
}