• 数据结构与算法-队列

    在这里插入图片描述

    队列

    🎈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
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    🔭3.2创建空队列

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

    • 1
    • 2
    • 3
    • 4
    • 5

    🔭3.3入队操作

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    🔭3.4出队操作

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    🔭3.5队列判空操作

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    🔭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;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    🔭3.7求队列长度

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

    • 1
    • 2
    • 3
    • 4

    🔭3.8全部代码实现

    #define _CRT_SECURE_NO_WARNINGS 1
#include 
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，否则返回0
	void 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;
	else
		return 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103

    ✅运行示例：
    在这里插入图片描述

    🎈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，否则返回0
	int QueueLength();//获取队列长度，即队列中元素个数

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    🔭4.3建立空队列

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

    • 1
    • 2
    • 3
    • 4
    • 5

    🔭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;//删除最后一个结点
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    🔭4.5入队操作

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    🔭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;
		}	
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    🔭4.7取队头元素

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

    • 1
    • 2
    • 3
    • 4
    • 5

    🔭4.8队列判空

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    🔭4.9求队列长度

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    🔭4.10打印队列

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    🔭4.11全部代码

    #define _CRT_SECURE_NO_WARNINGS 1
#include 
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，否则返回0
	void 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;
	else
		return 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121

    ✅运行示例：
    在这里插入图片描述

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

  • 相关阅读:
    【总结】maven 打包刷新下载依赖卡死
    Python爬虫:通过js逆向获取某视频平台上的视频的m3u8链接
    MySQL
    shell修改永久性别名，压缩与解压缩（zip gzip bzip2）文件上传预下载（sftp）
    探秘扩散模型：训练算法与采样算法的双重解读
    C# 将一种类型的数组转换为另一种类型的数组
    3.tomcat多实例和索引页
    RT-DETR个人整理向理解
    电力电子转战数字IC20220630day36——路科实验3
    ATSS介绍
  • 原文地址：https://blog.csdn.net/qq_73121173/article/details/133838723