当前位置：首页 > article >正文

数据结构-队列

article 2024/10/27 6:54:47

概念

队列的抽象数据类型定义

队列的顺序表示

假溢出

解决假溢出-循环队列

新的问题

队列满的条件思考

队列长度计算公式

队列的顺序实现

队列的元素类型定义

队列的初始化

求队列的长度

循环队列入队

循环队列出队

队列的链式表示和实现

链队列的类型定义

Qnode是什么

LinkQueue是什么

链队的入队操作

链队的出队操作

概念

队列（queue）是一种先进先出（Frist In Frist Out）的线性表，简称FIFO结构
在表一端插入（表尾，即aₙ端，称为队尾），在另一端（表头，即a₁端，称为队头）删
插入元素称为入队，删除元素称为出队

队列的抽象数据类型定义

ADT Queue{

数据对象：D = {aᵢ | aᵢ∈ElemSet, i = 1,2,...,n,n >= 0}

数据关系：R = {<aᵢ₋₁,aᵢ> | aᵢ₋₁,aᵢ∈D,i = 2,...,n} // 约定其中a₁端为队列头，aₙ端为队列尾

基本操作：

InitQueue(*Q)

操作结果：构造一个空队列Q

DestoryQueue(*Q)

条件：队列Q已存在

操作结果：销毁Q

ClearQueue(*Q)

条件：队列Q已存在

操作结果：将Q清空

QueueEmpty(Q)

条件：Q已存在

操作结果：若队列Q为空，返回TRUE;否则返回FALSE

GetHead(Q, *e)

条件：Q已存在且非空

操作结果：用e返回Q的队头元素

QueueLength(Q)

条件：Q已存在

操作结果：返回Q的元素个数，即队长

}ADT Queue

队列的顺序表示

引入两个指针
- front指针指向队头
- rear指针指向队尾元素的下一个位置
空队列：front == rear

假溢出

如：

这个队列的总个数不超过5个，front指针指向下标为2的位置，继续入队，就会产生数组越界的错误
可实际上，我们的队列在下标为0和1的地方还是空闲的，这种现象叫作“假溢出”

解决假溢出-循环队列

解决假溢出的办法就是，后面满了，就再从头开始，也就是头尾相接的循环
我们把队列的这种头尾相接的称为循环队列

使用刚才的例子，将rear改为指向下标为0的位置，就不会造成指针指向不明的问题了

接着再入队a₆、a₇

新的问题

空队列时，front == rear
现在的循环结构，当队列满时，也是fornt == rear
此时如何判断？

当队列空时，front == rear，当队列满时，我们修改其条件，保留一个元素空间
也就说，队列满时，数组中其实还有一个空间单元

两副图都表示队列满时

队列满的条件思考

队列的最大尺寸为MAXQSIZE
队列满的条件是：(rear + 1) % MAXQSIZE == front

此时，front = 0，rear = 4，（4 + 1) % 5 = 0，此时队列满

此时，front = 2，rear = 1，(1 + 1) % 5 = 2，此时队列满

队列长度计算公式

通用的计算队列长度公式：(rear - front +MAXQSIZE) % MAXQSIZE

当rear > front时
队列的长度为rear - front

当rear < front时
队列长度分为两段
一段是MAXQSIZE - front
一段是0 + rear
加在一起，队列长度：rear - front + MAXQSIZE

队列的顺序实现

队列的元素类型定义

typedef struct
{
	QElemType* base;  // 初始化的动态分配存储空间
	int front;  // 头指针
	int rear;  // 尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

队列的初始化

Status InitQueue(SqQueue* Q)
{

    /* 结构定义中使用了动态分配存储空间，需要分配数组空间 */
	Q->base = new QElemType[MAXQSIZE];

	if (!Q->base)exit(OVERFLOW);  // 存储分配失败
	
	// 头指针尾指针置为0，队列为空
	Q->front = 0;
	Q->rear = 0;  

	return OK;
}

求队列的长度

int QueueLength(SqQueue Q)
{
	return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}

循环队列入队

Status EnQueue(SqQueue* Q, QElemType e)
{
	// 判断队满
	if ((Q->rear + 1) % MAXQSIZE == Q->front) return ERROR; 
	
	// 新元素赋值给队尾
	Q->base[Q->rear] = e;  

	/* 
	队尾指针向后移一位置
	若到最后则转到数组头部
	*/
	Q->rear = (Q->rear + 1) % MAXQSIZE; 

	return OK;
}

循环队列出队

Status DeQueue(SqQueue* Q, QElemType* e)
{
	// 判断队空
	if (Q->front == Q->rear)return ERROR;

	// 将队头元素赋值给e
	*e = Q->base[Q->front];  

	/*
	队头指针向后移一位置
	若到最后则转到数组头部
	*/
	Q->front = (Q->front + 1) % MAXQSIZE; 

	return OK;
}

队列的链式表示和实现

若用户无法估计所用队列的长度，则采用链队列

链队列的类型定义

/* 结点的结构 */
typedef struct Qnode 
{
	QElemType data;
	struct Qnode* next;
}QNode, *QueuePtr;

/* 队列的链表结构 */
typedef struct
{
	QueuePtr front;  // 队头指针
	QueuePtr rear;  // 队尾指针
}LinkQueue;

Qnode是什么

struct Qnode：这是一个结构体类型，它定义了链队列中的一个节点，包含数据部分 data 和指向下一个节点的指针 next。
QNode：这是 struct Qnode 的一个别名。在C语言中，当你使用 typedef 为结构体定义了一个新名字后，你可以使用这个新名字来声明该类型的变量。例如，你可以使用 QNode node; 来创建一个节点变量（等价于struct Qnode node;）
*QueuePtr：这是一个指向 struct Qnode 类型的指针的别名。它定义了一个指针类型，该类型指向 Qnode 结构体。在代码中，你可以使用 QueuePtr 来声明指向节点的指针变量，例如 QueuePtr ptr;（等价于struct Qnode* ptr; ）

LinkQueue是什么

这次定义的是 LinkQueue 类型，它用于表示整个链队列
QueuePtr front;：这是 LinkQueue 结构体的一个成员，它是一个指向 Qnode 的指针，表示队列的头部
QueuePtr rear;：这是 LinkQueue 结构体的另一个成员，它也是一个指向 Qnode 的指针，表示队列的尾部

链队的入队操作

入队操作时，其实就是在链表尾部插入结点

Status EnQueue(LinkQueue* Q, QElemType e)
{
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));

	// 存储分配失败
	if (!s) exit(OVERFLOW);

	s->data = e;
	s->next = NULL;

	// 把新结点s赋值给原队尾结点的后继
	Q->rear->next = s;

	// 把当前s设置为队尾结点，rear指向s
	Q->rear = s;

	return OK;
}