链式队列
队列是一种受限制的特殊线性表,插入元素从队列的尾插入,删除元素从队列的头删除,所以最先插入(入队)的元素最先删除(出队),形成了“先进先出”的效果。
一般的队列是由数组实现的,并且用两个指针进行管理。一个头指针指向队列的头,另一个是尾指针,指向的是队列的尾部。而且队列头是连着队列尾的,实现了循环的效果,就像“Josephus环”那样。这种数组实现的队列最不好的地方就是有长度限制,而且处理不当会出现“溢出”。所以我通过链表的形式实现了队列,而不是数组。链表实现的队列继承了链表的特性,只是做了一些的限制。
下面是实现队列的详细代码:
Queue.h 队列的头文件
class Queue{ public: Queue():front(nullptr), rear(nullptr){}; ~Queue(); struct Node{ char Values; Node *Next; }; void Insert(char Values); void Show(); void Delete(); bool Empty(); private: Node *front; Node *rear; };
Queue.cpp 队列的源文件
#include <iostream> #include "Queue.h" using namespace std; void Queue::Insert(char Values){ Node *New = new Node; New->Values = Values; if(front == nullptr){ New->Next = New; front = New; rear = front; }else{ New->Next = front; rear->Next = New; rear = rear->Next; } } void Queue::Show(){ Node *p = front; if(front != nullptr){ do{ cout << p << "\t" << p->Values << "\t" << p->Next << endl; p = p->Next; }while(p != front); } cout << endl; } void Queue::Delete(){ Node *p = nullptr; if(front->Next != front){ rear->Next = front->Next; p = front->Next; delete front; front = p; }else{ delete front, rear; front = rear = nullptr; } } bool Queue::Empty(){ if(front != nullptr && rear != nullptr){ return false; }else{ return true; } } Queue::~Queue(){ delete front, rear; front = rear = nullptr; }
Main.cpp 程序的入口文件
#include <iostream> #include "Queue.h" using namespace std; int main(){ Queue QueueList; QueueList.Insert('a'); QueueList.Insert('b'); QueueList.Insert('c'); QueueList.Show(); QueueList.Delete(); QueueList.Show(); cout << QueueList.Empty() << endl; QueueList.Delete(); QueueList.Delete(); QueueList.Show(); cout << QueueList.Empty() << endl; system("pause"); return 0; }