一、基本概念

1、队列的定义

队列(Queue)，简称队，是一种只允许在一端插入另一端进行删除的操作受限的线性表。

向队列中插入元素称为入队或进队，删除元素则称为出队或离队。

对的规则，与现实生活中的排队是一样的，先来先服务，先进先出（First In First Out, FIFO）。

2、队列的特殊位置

每个队列都有两个特殊的重要的位置：队首与队尾。

队首（Front）：指队列中允许删除元素的一端，也称作队头。

队尾（Rear）：指队列中允许插入元素的一端。

3、基本操作

队列的基本操作有九个，涵盖初始化、增删改查和遍历与销毁。

Create()：创建一个空队列。

InitQueue()：初始化队列。

IsEmpty()：队列判空操作。

Length()：获取队列长度。

GetHead()：获取队首元素，但不删除队首元素。

EnQueue()：入队操作，队长加一。

DeQueue()：出队操作，队长减一。

Traverse()：遍历队列，将队列中的每个元素，按照从队首到队尾的顺序打印在屏幕上。

Clear()：将队列中的元素都清空掉。

Destroy()：销毁队列。

二、队列的实现

1、存储结构

用于实现队列的存储结构有顺序存储和链式存储两种，相应的队列称为顺序队列和链式队列。

顺序队列指分配一块连续的存储单元存放队列元素，并附设两个指针：队头指针和队尾指针，分别固定指向队头和队尾；当队头指针与队尾指针指向同一位置时，该队列为空。

链式队列是基于单链表实现的，这个单链表具有队头指针和队尾指针；链式队列的空对判断是判断队头指针或队尾指针是否悬空。

2、队列类型

常用的队列结构有顺序存储结构的非循环队列和循环队列，链式存储结构的普通链队和双端队列。实际运用中，顺序存储结构的非循环队列不使用，因为它有个致命缺陷——假溢出。

循环队列，是把存储队列元素的表从逻辑上视为一个环，当队首指针为Maxsize-1 后，再前进一个位置就自动到 0，具体通过除法取余运算实现。循环队列的初始状态是队头指针和队尾指针都为 0；队头指针进一：，队头指针刷新为当前队头指针值加一模表长；队尾指针进一：队尾指针刷新为当前队尾指针值加一模表长；出队或入队指针都按顺时针方向进一。循环队列队满的条件是：队尾指针加一模表长等于队头指针，队列为空的条件仍旧是队尾和队头指针指向同一地点，循环队列的元素个数为队尾指针减队头指针加表长后再模表长。循环队列是为了解决非循环队列的“假溢出”，即当以 rear==Maxsize 作为队满条件时，即便队列只有一个元素，都无法在进行入队了，此时再入队就会产生一种“假溢出”。

双端队列，是指允许两端都可以进行入队和出队操作的队列，此时队列的两端称为前端和后端。进队时，前端进的元素排列在后端进的元素的前面，后端进的元素排列在前端进的元素的后面；出队时，无论是前端出队还是后端出队，都是先出的元素排列在后出的元素前面。允许一端进行插入和删除，但另一端只允许插入的双端队列称为输出受限的双端队列，与此对应的，允许在一端进行插入和删除，另一端只允许删除的双端队列称为输入受限的双端队列。若限定双端队列从某个端插入的元素只能从该端删除，则双端队列就蜕变为栈。

三、循环队列C++实现

鉴于非循环的顺序队列的缺陷，因此不进行实例，而是实例循环队列。

实现创建空队列、初始化、队列判空与判满、获取队头元素与获取队长、元素入队与元素出队、队列元素遍历和队列清空操作。

具体代码如下：

#pragma once#include 
     
      using namespace std;constexpr auto maxsize = 20;class SeqQueue{
     private:	// 数据元素	int* data;	// 队头指针	int front;	// 队尾指针	int rear;	// 队长	int  len;public:	SeqQueue();	bool init(int a[], int len);	bool isEmpty();	bool isFull();	int getLen();	int getTop();	bool EnQueue(int value);	bool DeQueue(int& e);	void traverse();	bool clear();};// 构造空队列SeqQueue::SeqQueue(){
     	data = new int[maxsize];	front = rear = 0;	len = 0;}// 初始化队列bool SeqQueue::init(int a[], int len){
     	try {
     		for (int i = 0; i < len; i++)		{
     			data[rear] = a[i];			rear = (rear + 1) % maxsize;			this->len += 1;		}		return true;	}	catch (exception e)	{
     		cout << e.what() << endl;		return false;	}}//队列判空bool SeqQueue::isEmpty(){
     	if (rear == front)		return true;	return false;}// 队列判满bool SeqQueue::isFull(){
     	if ((rear + 1) % maxsize == front)		return true;	return false;}int SeqQueue::getLen(){
     	if (this->isEmpty())	{
     		cout << "队列为空！" << endl;		return 0;	}	return this->len;}int SeqQueue::getTop(){
     	if (!this->isEmpty())		return data[front];}// 入队操作bool SeqQueue::EnQueue(int value){
     	if (this->isFull())	{
     		cout << "队满，无法入队" << endl;		return false;	}	data[rear] = value;	rear = (rear + 1) % maxsize;	this->len += 1;	return true;}// 出队操作bool SeqQueue::DeQueue(int& e){
     	if (this->isEmpty())	{
     		cout << "对空，无法出队！" << endl;		return false;	}	e = data[front];	front = (front + 1) % maxsize;	this->len -= 1;	return true;}//遍历void SeqQueue::traverse(){
     	if (this->isEmpty())	{
     		cout << "队列为空！" << endl;		return;	}	int f = front;	int r = rear;	for (; f < rear; f++)		cout << data[f] << " ";	cout << endl;}// 清空队列bool SeqQueue::clear(){
     	if (this->isEmpty())	{
     		cout << "队列为空，不用进行清空操作！" << endl;		return false;	}	front = rear = 0;	len = 0;	return true;}

四、链队C++实现

#pragma once#include 
   
    using namespace std;class LinkNode{
   public:	int data;	LinkNode* next;	LinkNode()	{
   		data = 0;		next = NULL;	}};class LinkQueue{
   private:	// 队头指针	LinkNode* front;	// 队尾指针	LinkNode* rear;	int len;public:	LinkQueue();	bool init(int a[], int len);	bool isEmpty();	int getLen();	int getTop();	bool enQueue(int value);	bool deQueue(int& e);	void traverse();	bool clear();};LinkQueue::LinkQueue(){
   	front = rear = new LinkNode();	front->next = NULL;	len = 0;}bool LinkQueue::init(int a[], int len){
   	try	{
   		LinkNode* p;		for (int j = 0; j < len; j++)		{
   			p = new LinkNode();			p->data = a[j];			this->rear->next = p;			this->rear = p;			this->len += 1;		}		return true;	}	catch (exception e)	{
   		cout << e.what() << endl;		return false;	}}bool LinkQueue::isEmpty(){
   	if (this->front == NULL && this->rear == NULL)		return true;	return false;}int LinkQueue::getLen(){
   	if (this->isEmpty())		return 0;	return this->len;}int LinkQueue::getTop(){
   	return this->front->next->data;}bool LinkQueue::enQueue(int value){
   	try	{
   		LinkNode* p = new LinkNode();		p->data = value;		p->next = NULL;		this->rear->next = p;		this->rear = p;		this->len += 1;		return true;	}	catch (exception e)	{
   		cout << e.what() << endl;		return false;	}}bool LinkQueue::deQueue(int& e){
   	if (this->isEmpty())	{
   		cout << "队空，无法出队！" << endl;		return false;	}	LinkNode* p = this->front->next;	e = p->data;	this->front->next = p->next;	this->len -= 1;	if (this->rear == p)this->rear = this->front;	delete p;	return true;}void LinkQueue::traverse(){
   	if (this->isEmpty())	{
   		cout << "队空！" << endl;		return;	}	LinkNode* p = this->front->next;	for (int i = 0; i < this->len; i++)	{
   		cout << p->data << " ";		p = p->next;	}	cout << endl;}bool LinkQueue::clear(){
   	if (this->isEmpty())	{
   		cout << "队空！无需进行清空！" << endl;		return false;	}	LinkNode* p = this->front;	this->rear = this->front;	this->front->next = nullptr;	this->len = 0;	delete p;	return true;}