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

科技杭州网站建设/营销策划方案ppt

news 2025/6/30 20:21:47

科技杭州网站建设,营销策划方案ppt,济南好的网站建设公司排名,建设一个网站需要提供什么手续目录 😎前言认识队列队列的初始化队列判空数据队尾入队数据队头出队取队头数据取队尾数据队列数据的个数队列销毁总结 😎前言上次我们学习了栈及其实现，当然也少不它的好兄弟队列啦，今天我们开始队列的学习队…

😎前言

认识队列

队列的初始化

队列判空

数据队尾入队

数据队头出队

取队头数据

取队尾数据

队列数据的个数

队列销毁

总结

😎前言

上次我们学习了栈及其实现，当然也少不它的好兄弟队列啦，今天我们开始队列的学习
队列的性质是先进先出，就比如车辆进出隧道一般，它也是一种逻辑结构，依靠数组或者链表实现
在一些算法题我们也会运用到队列的进一步思想——优先队列（由二叉树实现），等到二叉树章节会给大家讲解的。

认识队列

队列和栈一样都是逻辑结构——由数组或者链表加以限制条件而成的，它的逻辑是先入先出，所以入数据是从队尾入，出数据就是从队头出

常见的应用就是银行的取号机，防止有人插队

可以发现如果用数组模拟队列的话，出队的时候就要频繁移动数组内的数据，不是很方便，也要考虑到扩容的问题，所以本篇选取链表的形式来实现队列

队列的初始化

队列本质上就是一个单链表，单链表又是由一个个节点组成，所以自然而然我们要先定义它的结点

typedef struct QNode
{struct QNode* next;QDataType val;
}QNode;

队列还需要一个指针指向它的队头，一个指针指向队尾，还有一个变量记录存储的数据的个数
所以此处可以选择再用一个结构体对其进行封装，这样操作起来就会简单许多

上图就是队列的基本框架了

typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;

有了基本结构，那么首先肯定还是对其就行初始化，这里只需要将两个指针都置空，size置0即可

老生常谈的问题，对于函数接口接受的队列来说不能为空，否则就相当于传了一个还没建立好的队列进去，直接assert断言暴打，这是每个函数接口都要用到的，下文就不赘述了

void QueueInit(Queue* q)
{assert(q);q->front = q->rear = NULL;q->size = 0;
}

队列判空

在取数据以及数据出队的时候，往往需要对队列进行判空操作，所以我们先将其封装成一个函数接口
可以提高代码的可读性
size及表示存储的数据个数，所以我们返回size==0这个条件判断表达式即可

以下为函数接口实现：

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{assert(q);return q->size == 0;
}

数据队尾入队

因为队列是不带头单向不循环链表，队尾入队就是给单链表尾插结点，所以链表学的扎实的同学应该可以反应过来这里需要分类讨论一下
一是队列为空的时候，这个时候插入数据就要改变front和rear指针的指向
二是链表不为空的时候，这个时候只需要改变front指针的指向
先malloc出新结点再进行插入操作
size记得++

以下为函数接口实现：

void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode=(QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail\n");return;}newnode->next = NULL;newnode->val = data;if (q->rear == NULL){assert(q->front==NULL);q->front = q->rear = newnode;}else{q->rear->next = newnode;q->rear = newnode;}q->size++;
}

数据队头出队

和队尾入队一样，此处仍需要分类讨论
一是普通情况，队头出队就是头删，先记录front的下一个结点next，然后free掉front指针指向的内存空间，然后再将next赋给front
二是只剩一个结点的时候，因为我们值移动front指针，所以操作完rear指针会依然指向被释放的那块空间，就存在野指针的问题
记得size需要--

以下为函数接口实现：

// 队头出队列 
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));//只有一个结点if (q->front->next == NULL){free(q->front);q->front = q->rear = NULL;}else{QNode* next = q->front->next;free(q->front);q->front = next;}q->size--;
}

取队头数据

如果队列为空，那么就不能返回数据，所以需要assert断言一下，这里也就用到了QueueEmpty函数接口啦
返回的是结点里存储的数据的值，所以函数返回类型是QDataType，不要思维固化地认为是int
返回front->val即可

以下为函数接口实现：

QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->front->val;
}

取队尾数据

如果队列为空，那么就不能返回数据，所以需要assert断言一下，这里也就用到了QueueEmpty函数接口啦
返回的是结点里存储的数据的值，所以函数返回类型是QDataType，不要思维固化地认为是int
返回rear->val即可

以下为函数接口实现：

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->rear->val;
}

队列数据的个数

上文提到了size代表存储的数据的个数，这里直接返回size即可

以下为函数接口实现：

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);return q->size;
}

队列销毁

本质上也就是单链表的销毁，在free掉一个结点前应该先记录其下一个结点
最后的front和rear指针置空，size置0

以下为函数接口实现：

void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->front = q->rear = NULL;q->size = 0;
}