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

佇列既然是一種比較特殊的線性表, 那麼它就有鏈式的表達方式

結合單循環鍊表和佇列就可以寫出單鏈佇列, 那麼佇列的具體知識在這裡不再累贅

在我寫的單鏈佇列中, 我設定了兩個佇列指標

• first : 佇列的第一個節點, 不含數據
• top : 永遠指向佇列的最後一個結點, 當佇列為空的時候, 其為空指標

我改寫了書上原來的方法, 我覺得原來的方法太麻煩了

直接用兩張 SVG 圖像表示單鏈佇列

空的單鏈佇列 :

帶有數據的單鏈佇列 :

下面是本人寫的原始碼

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

LinkedQueue.hpp :

#ifndef LINKEDQUEUE_LINKEDQUEUE_HPP
#define LINKEDQUEUE_LINKEDQUEUE_HPP

#include <iostream>
#include <cstdlib>

namespace LinkedQueue {
    using std::cin;
    using std::cout;
    using std::endl;
    class Node {
    protected :
        int data;
        Node *next;
    public :
        Node();
        Node(int data);
        ~Node();
        void insertData(int data);
        void insertNext(Node *next);
        int getData();
        Node *getNext();
    };
    class Queue {
    private :
        bool isEmpty();
    protected :
        Node *first;
        Node *top;
    public :
        Queue();
        ~Queue();
        long long int getFront();
        void enter(int data);
        void out();
        void clearQueue();
        void showQueue();
    };
}


#endif //LINKEDQUEUE_LINKEDQUEUE_HPP

LinkedQueue.cpp :

#include "LinkedQueue.hpp"

using namespace LinkedQueue;
Node::Node() {
    this->next = nullptr;
}
Node::Node(int data) {
    this->data = data;
    this->next = nullptr;
}
Node::~Node() {
    delete this->next;
}
void Node::insertNext(Node *next) {
    this->next = next;
}
void Node::insertData(int data) {
    this->data = data;
}
Node *Node::getNext() {
    return this->next;
}
int Node::getData() {
    return this->data;
}
Queue::Queue() {
    this->first = new Node;
    this->top = nullptr;
}
Queue::~Queue() {
    Node *node = this->first;
    this->top = nullptr;
    /* Delete all node from the queue. */
    if(node) {
        while(node->getNext() != nullptr) {
            Node *deleteNode = node;
            delete deleteNode;
            deleteNode->insertNext(nullptr);
            node = node->getNext();
        }
    }
    delete node;        //The last node has not been deleted.
    delete this->top;       //Delete the first node.
}
bool Queue::isEmpty() {
    if(!this->top) {
        return true;
    }
    return false;
}
long long int Queue::getFront() {
    if(isEmpty()) {
        return INT64_MIN;
    }
    return (long long int)this->top->getData();
}
void Queue::enter(int data) {
    auto *node = new Node;
    node->insertData(data);
    /* When the queue is empty : */
    if(!this->top) {
        this->first->insertNext(node);
        this->top = node;
        return;
    }
    Node *queue = this->first;
    /* Insert from the tail. */
    while(queue->getNext() != nullptr) {
        queue = queue->getNext();
    }
    queue->insertNext(node);
}
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->top->getData() << " has been out!" << endl;
    /* Change the top pointer and delete the pointer that has been out. */
    Node *node = this->top;
    this->first->insertNext(this->top->getNext());
    this->top = this->first->getNext();
    node->insertNext(nullptr);
    delete node;
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Queue::clearQueue() {
    auto *node = this->first->getNext();
    this->top = nullptr;
    /* Delete all node from the queue. */
    if(node) {
        while(node->getNext() != nullptr) {
            auto *deleteNode = node;
            node = node->getNext();
            deleteNode->insertNext(nullptr);
            delete deleteNode;
        }
    }
    delete node;        //Delete the last node that has not been deleted.
    this->first->insertNext(nullptr);       //Reset the first node's next node.
}
void Queue::showQueue() {
    if(isEmpty()) {
        return;
    }
    Node *node = this->first;       //iterator
    int count = 0;      //The size of queue
    /* Count the size of queue. */
    while(node->getNext() != nullptr) {
        count++;
        node = node->getNext();
    }
    /* Print the index : */
    cout << "Index : \t";
    for(int i = 1; i <= count; i++) {
        cout << i << "\t";
    }
    cout << endl << "Element : \t";
    node = this->first;
    /* Print the element : */
    while(node->getNext() != nullptr) {
        node = node->getNext();
        cout << node->getData() << "\t";
    }
    cout << endl;
    node = nullptr;
    delete node;
}

main.cpp :

#include "LinkedQueue.hpp"

using namespace LinkedQueue;

void menu();

int main(int argc, char *argv[]) {
    int choice;
    auto *queue = new Queue();
    long long int front;        //The front element
    int data;       //The data user want to enter to the queue
    /* Test module : To test whether the queue is normal */
    /*srand((unsigned)time(nullptr));
    system("clear");
    while(true) {
        choice = rand() % 3 + 1;
        switch(choice) {
            case 1 :
                data = rand() % 10;
                queue->enter(data);
                cout << "case 1" << endl;
                break;
            case 2 :
                queue->out();
                cout << "case 2" << endl;
                break;
            case 3 :
                queue->clearQueue();
                cout << "case 3" << endl;
                break;
            default :
                break;
        }
        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 : ";
}