本文已經過時, 最新文章請點擊 : 《【資料結構 – 重構】佇列與迴圈佇列》
佇列既然是一種比較特殊的線性表, 那麼它就有鏈式的表達方式
結合單循環鍊表和佇列就可以寫出單鏈佇列, 那麼佇列的具體知識在這裡不再累贅
在我寫的單鏈佇列中, 我設定了兩個佇列指標
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 : ";
}
自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《資料結構 : 單鏈佇列》https://jonny.vip/2018/02/20/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e5%96%ae%e9%8f%88%e4%bd%87%e5%88%97/
Leave a Reply