链式队列

队列是一种受限制的特殊线性表,插入元素从队列的尾插入,删除元素从队列的头删除,所以最先插入(入队)的元素最先删除(出队),形成了“先进先出”的效果。

一般的队列是由数组实现的,并且用两个指针进行管理。一个头指针指向队列的头,另一个是尾指针,指向的是队列的尾部。而且队列头是连着队列尾的,实现了循环的效果,就像“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;
}

标签:计算机, 程序, 设计, 常用, 算法, 链式, 队列

该文章由 Shiqi Qiu 原创并发布在 被遗忘的曙光 技术博客

转载请标明来源:https://fdawn.com/CPP/21.html

添加新评论