1.队列的简述
队列也是一种收限制的线性表，其特点是在一端进行插入的时，再另一端进行出队列的操作（删除操作）。把允许插
入操作的一端叫做队尾，允许删除操作的一端叫做队头。队列就像超市排队结账的人群，排在收银台一端的优先结账
离开，后面的依次排队并一直收银台前进，每出队列一个，向前走一步。
向队列插入元素称为入队，从队列中删除元素称为出队。不包含任何数据的队列称为空队列，队列也被称为先进先出
（First In First Out：FIFO）的线性表，换句话说，插入数据只能在队尾进行，删除操作只能在队头进行。
（后面还会有特殊情况：双端队列）
队头填充进四个元素
2.队列的基本顺序存储代码：
#define MaxSize 10//队列的初始化尺寸
template<typename T>
class SeqQueue
{
public:
SeqQueue();
~SeqQueue();
public:
bool EnQueue(const T& e);//入队列
bool DeQueue(T& e);//出队列
bool GetHead(T& e);//读取头元素
void ClearQueue();//清空队列
void DispList();//输出顺序队列中的所有元素
int ListLength();//获取队列长度（元素个数）
bool IsEmpty();//判断队列是否为空
bool IsFull();//判断队列是否已满
private:
T* m_data;
int m_front;//队头指针(数组下标)
int m_rear;//队尾指针（数组下标）,允许出队的那一端
};
template<typename T>
SeqQueue<T>::SeqQueue()
{
m_data = new T[MaxSize];
m_front = 0;
m_rear = 0;
}
template<typename T>
SeqQueue<T>::~SeqQueue()
{
delete[] m_data;
}
template<typename T>
bool SeqQueue<T>::EnQueue(const T& e)
{
if (IsFull() == true)
{
cout << "队列满了，不能再进行入队列操作了！" << endl;
return false;
}
m_data[m_rear] = e;
m_rear++;
return true;
}
template<typename T>
bool SeqQueue<T>::DeQueue(T& e)
{
if (IsEmpty() == true)
{
cout << "当前队列为空，不能进行出队列操作!" << endl;
return false;
}
e = m_data[m_front];
m_front++;
return true;
}
template<typename T>
bool SeqQueue<T>::GetHead(T& e)
{
if (IsEmpty() == true)
{
cout << "队列为空，无法进行获取头元素操作!" << endl;
return false;
}
e = m_data[m_front];
return true;
}
template<typename T>
void SeqQueue<T>::DispList()
{
for (int i = 0; i < m_rear;i++)
{
cout << m_data[i] << " ";
}
cout << endl;
}
template<typename T>
int SeqQueue<T>::ListLength()
{
return m_rear - m_front;
}
template<typename T>
bool SeqQueue<T>::IsEmpty()
{
if (m_front == m_rear)
{
return true;
}
return false;
}
template<typename T>
bool SeqQueue<T>::IsFull()
{
if (m_rear >= _Maximum)
{
return true;
}
return false;
}
template<typename T>
void SeqQueue<T>::ClearQueue()
{
m_rear = m_front = 0;
}
此时思考一个问题，当删除元素时（元素出队列时）会出现假饱和的情况，如上图m_data[0]和m_data[1]再进行出队列操作之后，这两个位置可以容纳新的元素，但m_rear没有回到原本的m_data[0]位置，因此需要引入一个新的队列结构，环形队列，m_rear这个位置可以从0到9再到0,周而复始不停的重复，保存的数据像在一个环状空间一样，这种头尾相连的队列结构就叫循环队列。
3.优化普通队列，成为可以循环接受数据的循环队列
循环队列代码如下：
#define MaxSize 10
template<typename T>
class RoundQueue
{
public:
RoundQueue();
~RoundQueue();
public:
bool EnQueue(const T& e);//入队列
bool DeQueue(T& e);//出队列
bool GetHead(T& e);//读取头元素
void ClearQueue();//清空队列
void DispList();//输出顺序队列中的所有元素
int ListLength();//获取队列长度（元素个数）
bool IsEmpty();//判断队列是否为空
bool IsFull();//判断队列是否已满
private:
T m_data;
int m_front;//队头指针(数组下标)
int m_rear;//队尾指针（数组下标）,允许出队的那一端
char m_tag;
};
template<typename T>
RoundQueue<T>::RoundQueue()
{
m_data = new T[MaxSize];
m_front = 0;
m_rear = 0;
m_tag = 0;//加入表示栈是否满的状态
}
template<typename T>
RoundQueue<T>::~RoundQueue()
{
delete[] m_data;
}
template<typename T>
bool RoundQueue<T>::EnQueue(const T& e)
{
if (IsFull () == true)
{
cout << "队列满了，不能再进行入队列操作了！" << endl;
return false;
}
m_tag = 1;
m_data[m_rear] = e;
m_rear = (m_rear + 1) % MaxSize;
return true;
}
template<typename T>
bool RoundQueue<T>::DeQueue(T& e)
{
if (IsEmpty() == true)
{
cout << "当前队列为空，不能进行出队列操作!" << endl;
return false;
}
m_tag = 0;
e = m_data[m_front];
m_front = (m_front + 1) % MaxSize;
return true;
}
template<typename T>
bool RoundQueue<T>::GetHead(T& e)
{
if (IsEmpty() == true)
{
cout << "队列为空，无法进行获取头元素操作!" << endl;
return false;
}
e = m_data[m_front];
return true;
}
template<typename T>
void RoundQueue<T>::DispList()
{
for (int i = m_front;i != m_rear)
{
cout << m_data[i] << " ";
i = (i + 1) % MaxSize;
}
cout << endl;
}
template<typename T>
bool RoundQueue<T>::IsFull()
{
if (m_rear == m_front && tag == 0)
{
return true;
}
return false;
}
template<typename T>
int RoundQueue<T>::ListLength()
{
return (m_rear + MaxSize - m_front) % MaxSize;
}
template<typename T>
bool RoundQueue<T>::IsEmpty()
{
if (m_front == m_rear && tag == 0)
{
return true;
}
return false;
}
template<typename T>
void RoundQueue<T>::ClearQueue()
{
m_rear = m_front = m_tag = 0;
}
循环队列队列满的情况，如下图：
4.队列的链式结构实现
和前面所有的数据结构一样，队列也有链式结构
空队列的情况：
插入两个元素之后的队列：
实现代码如下图所示：
template<typename T>
struct QueueNode
{
T data;//数据域
QueueNode<T>* next;//指针域，指向下一个节点
};
template<typename T>
class LinkQueue
{
public:
LinkQueue();
~LinkQueue();
public:
bool EnQueue(const T& e);//入队
bool DeQueue(T& e);//出队
bool GetHead(T& e);//读取头元素
void DispList();//输出链式队列中的所有元素
int ListLength();//获取链式队列的长度（链式表元素个数）
bool IsEmpty();//判断链式队列是否为空
private:
QueueNode<T>* m_front;//头指针，这一端允许出队（删除）
QueueNode<T>* m_rear;//尾指针记录入队
int m_length;
};
template<typename T>
LinkQueue<T>::LinkQueue()
{
m_front = new QueueNode<T>;
m_front->next = nullptr;
m_rear = m_front;
m_length = 0;
}
template<typename T>
LinkQueue<T>::~LinkQueue()
{
QueueNode<T>* pnode = m_front->next;
QueueNode<T>* ptmp;
while (pnode != nullptr)
{
ptmp = pnode;
pnode = pnode->next;
delete ptmp;
}
delete m_front;
m_front = m_rear = nullptr;
m_length = 0;
}
template<typename T>
bool LinkQueue<T>::EnQueue(const T& e)
{
QueueNode<T>* node = new QueueNode<T>;
node->data = e;
node->next = nullptr;
m_rear->next = node;//新节点插入到头指针之后
m_rear = node;//更新队尾指针的位置
m_length++;
return true;
}
template<typename T>
bool LinkQueue<T>::DeQueue(T& e)
{
if (IsEmpty() == true)
{
cout << "当前链式队列为空，无法进行出队列操作!" << endl;
return false;
}
QueueNode<T>* p_willdel = m_front->next;
e = p_willdel->data;
m_front->next = p_willdel->next;
if (m_rear == p_willdel) //队列中只有一个元素，删除之后，m_rear和m_front相连
{
m_rear = m_front;
}
delete p_willdel;
m_length--;
return true;
}
template<typename T>
void LinkQueue<T>::DispList()
{
QueueNode<T>* p = m_front->next;
while (p != nullptr)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
template<typename T>
int LinkQueue<T>::ListLength()
{
return m_length;
}
template<typename T>
bool LinkQueue<T>::IsEmpty()
{
if (m_front == m_rear)
{
return true;
}
return false;
}
5.双端队列
前面的几种队列都可以看成普通的队列，还有一种变形的队列-双端队列。双端队列就是允许两端插入和删除数据。STL中提供的名字叫做deque的容器，就是一个典型的双端队列。双端队列的存取如图所示：文章来源：https://www.toymoban.com/news/detail-752488.html
也可以对双端队列进行一系列的限制，可以有输入受限的的双端队列和输出受限的双端队列，如图为输入受限的双端队列，只能一端输入，两端输出：
也可也一端输出，两端输入的双端队列，如图：
代码实现如下：文章来源地址https://www.toymoban.com/news/detail-752488.html
// 节点
template<class T>
class Node
{
public:
T data;
Node<T> *left;
Node<T> *right;
Node() {
data= 0;
left = right = nullptr;
}
Node(T n) {
data= n;
left = right = nullptr;
}
};
// 双端队列
template<class T>
class double_ended_queue {
public:
Node<T>*queue_left, *queue_right;
int num;
int size;
double_ended_queue() {
queue_left=queue_right = nullptr;
num = 0;
size = 10;
}
void IsEmpty();
void IsFull();
void AddLeft(T);
void AddRight(T);
void DeleteLeft();
void DeleteRight();
void Print();
};
template<class T>
void double_ended_queue<T>::IsEmpty() {
num == 0 ? cout << "YES" << endl : cout << "NO" << endl;
}
template<class T>
void double_ended_queue<T>::IsFull() {
num == size ? cout << "YES" << endl : cout << "NO" << endl;
}
template<class T>
void double_ended_queue<T>::Print() {
if (num == 0)
{
cout << "EMPTY" << endl;
return;
}
Node<T>*p = queue_left;
for (int i = 0; i < num-1; i++) {
cout << p->data << " ";
p = p->right;
}
cout << p->data << endl;
}
template<class T>
void double_ended_queue<T>::AddLeft(T n) {
Node<T>*p = new Node<T>(n);
if (num == 0)
{
queue_left =queue_right=p;
queue_left->left =queue_left->right=nullptr;
num++;
}
else{
if (num == size)
{
cout << "FULL ";
Print();
return;
}
queue_left->left = p;
p->right = queue_left;
queue_left = queue_left->left;
num++;
}
Print();
}
template<class T>
void double_ended_queue<T>::AddRight(T n) {
Node<T>*p = new Node<T>(n);
if (num == 0)
{
queue_left = queue_right = p;
queue_right->left = queue_right->right = nullptr;
num++;
}
else {
if (num == size)
{
cout << "FULL " ;
Print();
return;
}
queue_right->right = p;
p->left = queue_right;
queue_right = queue_right->right;
num++;
}
Print();
}
template<class T>
void double_ended_queue<T>::DeleteLeft() {
if (num == 0) {
cout << "EMPTY" << endl;
return;
}
Node<T>*p = queue_left->right;
delete queue_left;
queue_left = p;
num--;
Print();
}
到了这里，关于C++数据结构之队列详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![数据结构03：栈、队列和数组 队习题01[C++]](https://imgs.yssmx.com/Uploads/2024/04/849898-1.png)
