目录
一、前言
? ? ? ? 本文将详细介绍队列以及用C++实现队列的封装，代码复制可使用，重点介绍顺序循环队列，链队列只稍加讨论。
二、队列的定义和特点?
? ? ? ? 队列是一种先进先出（First In First Out，FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这与日常生活中排队一样，最早进入队列的元素最先离开。在队列中允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。假设队列为Q = (a1，a2，...，an)，那么a1就是队头元素，an则是队尾元素。如果队列中的元素是按照a1，a2，...，an的顺序入队的，则退出队列也只能按照这个次序依次退出（先进先出）。如下图所示。
三、循环队列
1.存储表示
? ? ? ? 循环队列采用顺序存储结构，在此用数组实现，另外附设两个整型变量 front 和 rear 分别指示队列头元素及队列尾元素的位置（后面分别称为头指针和尾指针）。将循环队列封装成一个模板类，类属性如下。
//采用类模板后续具体使用时可指定任意数据类型
//如果对模板不熟悉可以将代码中所有的T替换为熟悉的整型int
template<class T>
class SqQueue
{
private:
T *base; //队列存储空间基地址
int front; //队头指针
int rear; //队尾指针
int m_capacity; //队列容量
};? ? ? ? 初始化创建队列时，令front = rear = 0，每当插入新的队列元素时，尾指针rear增1，每当删除队头元素时，头指针front增1.因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，如下图所示。
????????此时我门只是用一个数组来表示队列，但是循环在哪似乎没体现出来?咱接着看，上述情况其实会出现一个问题：
对于空间为M的数组
当head = 0,tail = M时，再有元素入队发生溢出——真溢出
当head !=?0,tail = M时，再有元素入队发生溢出——假溢出
????????为了解决这一问题，便引出了循环队列。基本思想：把队列设想成环形，让base[0]接在base[M-1]之后，若rear==M,则令rear=0。具体实现见下图。
利用了模运算实现了循环队列，这样一来上述假溢出的问题便得到了解决，但是又出现了一个新问题 ，即如何区分队空和队满？该问题具体描述如下图。
????????可见循环队列中，队空和队满两种情况都有front==rear，故不能以此条件来区分。在此我们通过少用一个元素空间的方法来解决此问题，即队列空间大小为M时，有M-1个元素就认为是队满。这样判断队空的条件不变，即当头尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等于头指针，则认为队满。因此：
队空的条件：front == rear
队满的条件：(rear + 1) % M == front
少用一个元素空间后的队列如下图所示。
2.操作实现?
? ? ? ? 明白了循环队列的存储结构后，其队列操作实现起来就相对简单了，在此简单介绍一些算法思想，具体操作参考循环队列完整代码的注释也能轻松理解。
初始化：构造函数中传入一个参数，为队列分配一个容量为该参数大小的数组空间，base指向数组空间首地址；头指针尾指针置0表示队空；
判空：若rear == front则队空。使用队列的过程中会经常判断队列是否为空。
入队：判断队列是否已满，若满则执行空操作；将新元素插入队尾；队尾指针加1。
出队：判断队列是否为空，若空则执行空操作；保存队头元素；队头指针加1。
//采用类模板后续具体使用时可指定任意数据类型
//如果对模板不熟悉可以将代码中所有的T替换为熟悉的整型int
template<class T>
class SqQueue
{
private:
T *base; //队列存储空间基地址
int front; //队头指针
int rear; //队尾指针
int m_capacity; //队列容量
public:
//构造函数，构造一个空队列
SqQueue(int capacity)
{
base = new T[capacity]; //在堆区为队列开辟大小为capacity的数组空间
m_capacity = capacity; //队列容量
front = rear = 0; //头尾指针同时置为0，队列为空
}
//析构函数，销毁队列
~SqQueue()
{
delete [] base;
}
//返回队列元素个数
int getLength()
{
return (rear - front + m_capacity) % m_capacity;
}
//判空
bool empty()
{
if(rear == front)
return true;
return false;
}
//入队操作
void enQueue(T e)
{
//判断是否队满
if((rear + 1) % m_capacity == front)
{
cout << "SqQueue::enQueue()调用失败，队列已满。" << endl;
exit(-1);
}
//将新元素插入队尾
base[rear] = e;
//队尾指针加1
rear = (rear + 1) % m_capacity;
}
//出队操作
void deQueue(T &e)
{
//判空
if(empty())
{
cout << "SqQueue::deQueue()调用失败，队列为空。" << endl;
exit(-1);
}
//保存队头元素
e = base[front];
//队头指针加1
front = (front + 1) % m_capacity;
}
//获取队头元素
T getHead()
{
//判空
if(empty())
{
cout << "SqQueue::getHead()调用失败，队列为空。" << endl;
exit(-1);
}
//返回队头元素
return base[front];
}
};?四、链队列
? ? ? ? 链队是指采用链式存储结构实现的队列，通常用单链表来表示。如图所示。
? ? ? ? 链队列的队列运算指针变化状况如下图所示，在此不作具体讨论，代码中会给出具体注释。
/*链队列*/
#pragma once
/*队列元素结点类型*/
template <typename T>
struct QNode
{
T data;
QNode* next;
};
/*队列类*/
template <typename T>
class Queue
{
public:
//构造函数，构造一个空队列
Queue()
{
front = rear = new QNode<T>;//初始化头尾指针均指向头结点
front->next = nullptr;
len = 0;
}
//析构函数，销毁一个队列
~Queue()
{
QNode<T>* p = front;
while (p)
{
QNode<T>* q = p;
p = p->next;
delete q;
}
}
//清空队列
void clear()
{
QNode<T>* p = front->next;
while (p)
{
QNode<T>* q = p;
p = p->next;
delete q;
}
front->next = nullptr;
rear = front;
len = 0;
}
//判空
bool empty()
{
return front == rear;
}
//获取队头元素
bool getHead(T& e)
{
if (empty())
return false;
e = front->next->data;
return true;
}
//*元素e入队
void enQueue(T e)
{
QNode<T>* p = new QNode<T>;
p->data = e;
//插进队尾
p->next = nullptr;
rear->next = p;
//更新队尾
rear = p;
len++;
}
//队头元素出队
bool deQueue(T& e)
{
if (empty())
return false;
QNode<T>* p = front->next;//p记录队头元素
e = p->data;
front->next = p->next;//删除队头元素
if (rear == p)//只有一个元素
rear = front;//删除后变空队列
delete p;
len--;
return true;
}
//遍历
void traverse(void (*visit)(T))
{
QNode<T>* p = front->next;
while (p)
{
visit(p->data);
p = p->next;
}
}
private:
QNode<T>* front;//队头指针
QNode<T>* rear;//队尾指针
int len;//元素个数
};?五、总结
????????感谢大家的观看，如有错误或者令你不解的地方可以评论区讨论，我都会一一回复的。后续会一直更新数据结构方面的内容。