个人主页:17_Kevin-CSDN博客 专栏:《数据结构》
队列是只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出
FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头
二、队列的操作
队列有以下几种常见的操作:
队列可以使用多种数据结构来实现,如数组、链表等。
但是用链表实现队列效果更优,因为如果是数组的话,队列每次需要从头上出数据,这样就需要将数组后面的数据依次往前挪动,这样会增加时间复杂度,不如使用链表直接free掉队头数据快捷。
typedef int QDataType;
typedef struct QueueNode
{
int val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
创建一个结构体类型QNode来作为队列中每个节点的数据存储结构体,用Queue作为存储队头和队尾还有队列长度的结构体类型。
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
和链表的初始化大同小异。
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
首先检查传入的pq队列是不是已经没有数据了,然后创建一个Queue类型的变量cur和next用来遍历销毁队列。在循环中用next来指向cur的下一个数据,然后free掉现在cur的数据,持续推动向前,一个接一个销毁。
在 while (cur)
循环结束后,cur
确实已经被设置为 NULL
,但是将队列的头指针和尾指针都设置为 NULL
是为了确保队列的状态被正确地重置为空闲状态。
即使 cur
已经是 NULL
,队列的其他成员变量(如 size
)仍然可能包含不正确的值。通过将头指针和尾指针都设置为 NULL
,可以确保队列被完全清空,并避免任何潜在的错误或未初始化的状态。
// 入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
if (pq->ptail)
{
pq->ptail->next = newnode;//将当前尾的next设置为newnode
pq->ptail = newnode;//更新pq的尾节点,所以当前尾节点为newnode
}
else
{
pq->phead = pq->ptail = newnode;
}
pq->size++;
}
在创建空间并分配后,根据队列的当前状态进行不同的操作。如果队列的尾指针 pq->ptail
不为 NULL
,则将 newnode
插入到队列的尾部。首先,将 pq->ptail->next
设置为 newnode
,将 newnode
连接到队列的尾部。然后,将 pq->ptail
更新为 newnode
,以便后续的操作可以正确地找到队列的尾部。如果队列的尾指针为 NULL
,表示队列为空,此时将 newnode
设置为队列的头指针和尾指针,即 pq->phead = pq->ptail = newnode
。
// 出队列
void QueuePop(Queue* pq)
{
assert(pq);
// 0个节点
// 温柔检查
//if (pq->phead == NULL)
// return;
// 暴力检查
assert(pq->phead != NULL);
// 一个节点
// 多个节点
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
// 暴力检查
assert(pq->phead != NULL);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
// 暴力检查
assert(pq->ptail != NULL);
return pq->ptail->val;
}
队列在计算机科学中有许多应用场景,以下是一些常见的例子:消息队列:在分布式系统中,消息队列用于在不同的进程或节点之间传递消息。
I'm Kevin, and we'll see you next time