数据结构与算法-队列

🎈1.队列的定义

队列是线性表的特例，它也是一种操作受限的线性表。队列只允许在表的一端进行插入，在另一端进行删除。把允许插入的一端称为队尾，允许删除的一端称为队头。从队尾插入元素的操作称为入队，从队头删除元素的操作称为出队。队列是一种先进先出的线性表，即每个元素按照进队的次序出队。

注：其中a1为队头，an为队尾，front指向队头，rear指向队尾（实际上是队尾元素的下一个位置）

🎈2.队列的抽象数据类型定义

🎈3.顺序队列（循环队列）

队列的顺序存储结构称为顺序队列，一般用循环队列表示。顺序队列是用一组地址连续的存储单元（例如：数组）依次存放从队头到队尾的元素，由于队列的队头和队尾的位置是变化的，因此需要定义一个指向队头的指针（front），也称头指针；一个指向队尾的指针（rear）,也称尾指针。

将存储队列的数组看成是头尾相接的圆环，并形成循环存储空间，即允许队列直接从数组中下标最大的位置延续到下标最小的位置，这个操作可以通过取模运算实现。队列的这种头尾相接的顺序存储结构称为循环队列。循环队列如图所示，灰色区域表示队列中已经存储数据元素的存储空间，空白区域则表示空闲存储空间。

🔭3.1循环队列

在循环队列中进行入队、出队操作，头尾指针均加1，依次向前移动。只不过当头尾指针指向存储空间上届（QueueSize-1）时，其加1操作的结果是指向存储空间的下界0.这种循环意义下的加1操作可以利用模运算来实现，即i=(i+1)%QueueSize.

注：1.空队列的判定条件：rear==front
2.当a出队后，头指针front的移动方式为：front = (front+1) % QueueSize
3.当a,b,c,d入队后，尾指针rear的移动方式为：rear = (rear+1)%QueueSize.
4.队列满的判定条件是：front=(rear+1)%QueueSize.

🔭3.1循环队列类定义

#define QueueSize 100
typedef int QElemType;
class SqQueue
{
private:QElemType* base;int front;int rear;
public:SqQueue();//构造函数，建立空队列~SqQueue()//析构函数，销毁队列{delete[]base;front = rear = 0;}QElemType GetHead();//取队头元素void EnQueue(QElemType e);//元素e入队void DeQueue(QElemType& e);//队列元素出队int EmptyQueue();//队列判空，若队列为空返回1，否则返回0
};

🔭3.2创建空队列

SqQueue::SqQueue()//构造函数
{base = new QElemType[QueueSize];front = rear = 0;
}

🔭3.3入队操作

void SqQueue::EnQueue(QElemType e)
{if (front == (rear + 1) % QueueSize)return;else{base[rear] = e;rear = (rear + 1) % QueueSize;}
}

🔭3.4出队操作

void SqQueue::DeQueue(QElemType& e)
{if (front == rear)//队列为空，无法出队return;else{e = base[front];front = (front + 1) % QueueSize;}
}

🔭3.5队列判空操作

int SqQueue::EmptyQueue()
{if (rear == front)return 1;elsereturn 0;
}

🔭3.6打印循环队列

void SqQueue::print(SqQueue& p)
{if (p.EmptyQueue())cout << "Queue is empty!" << endl;QElemType head = p.front;cout << "Queue elements: ";while (head != p.rear){cout << p.base[head] << " ";head = (head + 1) % QueueSize;}
}

🔭3.7求队列长度

void SqQueue::Length()
{cout << (rear - front + QueueSize) % QueueSize << endl;
}

🔭3.8全部代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#define QueueSize 100
typedef int QElemType;
class SqQueue
{
private:QElemType* base;int front;int rear;
public:SqQueue();//构造函数，建立空队列~SqQueue()//析构函数，销毁队列{delete[]base;front = rear = 0;}QElemType GetHead();//取队头元素void EnQueue(QElemType e);//元素e入队void DeQueue();//队列元素出队int EmptyQueue();//队列判空，若队列为空返回1，否则返回0void Length();//打印队列void print(SqQueue& p);
};
SqQueue::SqQueue()//构造函数
{base = new QElemType[QueueSize];front = rear = 0;
}
void SqQueue::EnQueue(QElemType e)
{if (front == (rear + 1) % QueueSize)return;else{base[rear] = e;rear = (rear + 1) % QueueSize;}
}
void SqQueue::DeQueue()
{QElemType e;if (front == rear)return;else{e = base[front];front = (front + 1) % QueueSize;}
}
int SqQueue::EmptyQueue()
{if (rear == front)return 1;elsereturn 0;
}
QElemType SqQueue::GetHead()
{if (rear == front)return 0;else{cout << base[front] << endl;return 1;}
}
void SqQueue::Length()
{cout << (rear - front + QueueSize) % QueueSize << endl;
}
void SqQueue::print(SqQueue& p)
{if (p.EmptyQueue())cout << "Queue is empty!" << endl;QElemType head = p.front;cout << "Queue elements: ";while (head != p.rear){cout << p.base[head] << " ";head = (head + 1) % QueueSize;}
}
int main()
{SqQueue p;p.EnQueue(1);p.EnQueue(2);p.EnQueue(3);p.EnQueue(4);p.EnQueue(5);p.EnQueue(6);p.EnQueue(7);p.EnQueue(8);p.EnQueue(9);p.EnQueue(10);p.Length();p.DeQueue();p.GetHead();p.print(p);return 0;
}

✅运行示例：

🎈4.链队列

队列的链式存储结构称为链队列。链队列可通过带头结点的单链表来实现。此时只允许在单链表的表首进行删除操作和在单链表的表尾进行插入操作。为此，需要设立两个指针，一个指向头结点，称为表首指针（front）,另一个指向队尾结点，称为表尾指针（rear）.根据队列先进先出的特征，链队列是仅在表头删除元素和表尾插入元素的单链表。

🔭4.1链队列动态示意图

🔭4.2链队列的类定义

typedef int QElemType;
//链队列的数据结点类型定义如下：
typedef struct QNode
{QElemType data;QNode* next;
}QNode;
//链队结点类型定义如下：
typedef struct
{QNode* front;QNode* rear;
}LinkQNode;
class LinkQueue
{
private:LinkQNode q;
public:LinkQueue();//构造函数，建立空队列~LinkQueue();QElemType GetHead();//取队头元素void EnQueue(QElemType e);//元素e入队void DeQueue(QElemType& e);//队头元素出队int EmptyQueue();//队列判空，若队列为空则返回1，否则返回0int QueueLength();//获取队列长度，即队列中元素个数

🔭4.3建立空队列

LinkQueue::LinkQueue()
{q.front = q.rear = new QNode;q.front->next = NULL;
}

🔭4.4销毁队列

LinkQueue::~LinkQueue()
{QNode* p = q.front->next;while (p){q.front->next = p->next;delete p;p = q.front->next;}delete q.front;//删除最后一个结点
}

🔭4.5入队操作

void LinkQueue::EnQueue(QElemType e)
{QNode* s = new QNode;s->data = e;s->next = NULL;q.rear->next = s;q.rear = s;
}

🔭4.6出队操作

void LinkQueue::DeQueue(QElemType& e)
{if (q.front == q.rear)return;else{QNode* p = q.front->next;q.front->next = p->next;e = p->data;if (p == q.rear){q.rear = q.front;delete p;}	}
}

🔭4.7取队头元素

QElemType LinkQueue::GetHead()
{if (q.front->next != NULL)return q.front->next->data;
}

🔭4.8队列判空

int LinkQueue::EmptyQueue()
{if (q.front->next != NULL)return 0;elsereturn 1;
}

🔭4.9求队列长度

void LinkQueue::QueueLength()
{int length = 0;QNode* p = q.front->next;while (p){length++;p = p->next;}cout << "该链队列的长度为：" << length << endl;
}

🔭4.10打印队列

void LinkQueue::print()
{QNode* p = q.front->next;while (p){cout << p->data<<" ";p = p->next;}cout << endl;
}

🔭4.11全部代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
typedef int QElemType;
//链队列的数据结点类型定义如下：
typedef struct QNode
{QElemType data;QNode* next;
}QNode;
//链队结点类型定义如下：
typedef struct
{QNode* front;QNode* rear;
}LinkQNode;
class LinkQueue
{
private:LinkQNode q;
public:LinkQueue();//构造函数，建立空队列~LinkQueue();QElemType GetHead();//取队头元素void EnQueue(QElemType e);//元素e入队void DeQueue();//队头元素出队int EmptyQueue();//队列判空，若队列为空则返回1，否则返回0void QueueLength();//获取队列长度，即队列中元素个数void print();
};
LinkQueue::LinkQueue()
{q.front = q.rear = new QNode;q.front->next = NULL;
}
LinkQueue::~LinkQueue()
{QNode* p = q.front->next;while (p){q.front->next = p->next;delete p;p = q.front->next;}delete q.front;//删除最后一个结点
}
void LinkQueue::EnQueue(QElemType e)
{QNode* s = new QNode;s->data = e;s->next = NULL;q.rear->next = s;q.rear = s;
}
void LinkQueue::DeQueue()
{QElemType e;if (q.front == q.rear)return;else{QNode* p = q.front->next;q.front->next = p->next;e = p->data;if (p == q.rear){q.rear = q.front;delete p;}	}
}
QElemType LinkQueue::GetHead()
{if (q.front->next != NULL)cout<< q.front->next->data<<endl;return 1;
}
int LinkQueue::EmptyQueue()
{if (q.front->next != NULL)return 0;elsereturn 1;
}
void LinkQueue::QueueLength()
{int length = 0;QNode* p = q.front->next;while (p){length++;p = p->next;}cout << "该链队列的长度为：" << length << endl;
}
void LinkQueue::print()
{QNode* p = q.front->next;while (p){cout << p->data<<" ";p = p->next;}cout << endl;
}int main()
{LinkQueue q;q.EnQueue(1);q.EnQueue(2);q.EnQueue(3);q.EnQueue(4);q.EnQueue(5);q.print();q.DeQueue();q.print();q.GetHead();q.QueueLength();return 0;
}

✅运行示例：

好啦，关于队列的知识到这里就结束啦，后期会继续更新数据结构与算法的相关知识，欢迎大家持续关注、点赞和评论！❤️❤️❤️