初阶数据结构
第一章 时间复杂度和空间复杂度
第二章 动态顺序表的实现
第三章 单向链表的讲解与实现
第四章 带头双向链表的讲解与实现
第五章 栈的讲解与实现
第六章 队列的讲解与实现
文章目录
- 初阶数据结构
- 前言
- 一、什么是队列？
- 二、队列的定义：
- 三、接口函数的实现：
* - 1、初始化：
- 2、判断是否为空：
- 3、插入：
- 4、删除：
- 5、访问队头：
- 6、访问队尾：
- 7、元素个数：
- 8、销毁：
- 四、队列中元素的访问：
前言
在上一章节中，我们了解到栈这种数据结构的特点是先进后出，那么今天所讲解的队列的特点则恰恰与之相反。队列这种数据结构的特点是：先进先出，后进后出。接下来我们将对其进行详细地讲解。
一、什么是队列？
队列在生活中是非常常见的，比如我们做核酸的时候，都会以队列的形式排队。很明显，先排队的人就可以先做核酸，后排队的人只能后做核酸。这其实就是队列这种结构的特点，那么其逻辑结构如下图所示：
; 二、队列的定义：
typedef int ElementType;
typedef struct QueueNode
{
struct QueueNode* next;
ElementType data;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
在上述的定义中，我们先定义了队列中的元素，很明显可以看出我们是用链表的形式来实现队列结构的。其实原因很简单，队列涉及头删的问题，而顺序表中头删的时间复杂度是 O(N)。很明显，顺序表实现队列的效率是非常低的。所以，我们采用链表的形式。
当我们定义好节点之后，我们再来看队列这种数据结构。这种结构中最重要的其实就是尾插和头删这两种功能。而我们在前面的章节中学习单向链表的时候，我们发现，每次尾插的时候都需要寻找尾部节点。该过程的是将复杂度是 O(N)。其效率是很低的。因此，我们可以实现定义一个尾指针来记录尾部节点。因此我们就有了另外一个关于队列的结构体，这个结构体中定义了两个变量，一个是头指针，一个是尾指针。
三、接口函数的实现：
1、初始化：
队列的初始化非常简单，就是将两个指针都指向空指针即可。
void QueueInit(Queue* q)
{
assert(q);
q->head = NULL;
q->tail = NULL;
}
2、判断是否为空：
头指针指向的是第一个元素，那么如果头指针指向的是空，那么这个队列就为空。
assert(q);
if (q->head == NULL)
{
return true;
}
else
{
return false;
}
3、插入：
队列的插入方式是尾插，在单向无头链表中尾插需要考虑空队列的情况。
第一种情况：队列不为空
这种情况下，我们需要做两件事情，一件事是将当前的尾节点的指针域指向新的节点，第二件事就是更新我们的尾指针，让我们的尾指针指向我们新的尾部节点。
第二种情况：队列为空：
这种情况下，我们也需要做两件事情，
第一件事是将头指针指向新的节点，由于只有一个节点，所以这个节点即使尾部，也是头部。
所以第二件事，就是将尾指针也指向新的节点。
void QueuePush(Queue* q,ElementType dat)
{
assert(q);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
printf("Failed to creat new space!\n");
exit(-1);
}
newnode->next = NULL;
newnode->data = dat;
if (q->tail != NULL)
{
q->tail->next = newnode;
q->tail = newnode;
}
else
{
q->head = newnode;
q->tail = newnode;
}
}
4、删除：
删除分为三种情况，
第一种情况：
队列不为空，此时我们需要先释放头节点，然后将头指针向后移动一个位置，更新头部指针。
第二种情况：
队列为空的时候，我们是不需要删除的，如果我们强行删除的话，会出现访问野指针的情况。
第三种情况：
队列中只有一个元素。（ 这种情况最需要注意！！！） 避免野指针！！！
void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
QueueNode* nex = q->head->next;
free(q->head);
q->head = nex;
if (q->head == NULL)
{
q->tail = NULL;
}
}
5、访问队头：
这个函数就很简单了，先判断一下队列是否为空，如果不为空则返回头节点的数据。
ElementType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->head->data;
}
6、访问队尾：
思路和访问队头的思路一样。
ElementType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->tail->data;
}
7、元素个数：
元素个数的计算有两种方法，第一种方法是我们在队列的结构体中创建一个变量来记录个数。另外一种方式就是遍历一遍整个队列。
遍历的方法就是，我们创建一个cur指针指向头部，然后偏移cur。
int QueueSize(Queue* q)
{
assert(q);
int size = 0;
QueueNode* cur = q->head;
while (cur != NULL)
{
size++;
cur = cur->next;
}
return size;
}
8、销毁：
销毁的逻辑和链表中的销毁函数的思路是一致的。
但是最后别忘了将头指针和尾指针设置为空，避免野指针的出现。
void QueueDestory(Queue* q)
{
assert(q);
QueueNode* cur = q->head;
while (cur != NULL)
{
QueueNode* nex = cur->next;
free(cur);
cur = nex;
}
q->head = NULL;
q->tail = NULL;
}
四、队列中元素的访问：
由于队列中的元素满足先进先出，后进后出的特点，所以我们只能访问头尾，想要访问第二个元素，必须删掉队头才行。因此，我们就可以结合上面的接口函数，模拟队列的实现。
#include"Queue.h"
void TestQueue1()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
ElementType front = QueueFront(&q);
printf("%d ", front);
QueuePop(&q);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
ElementType front = QueueFront(&q);
printf("%d ", front);
QueuePop(&q);
}
printf("\n");
}
int main()
{
TestQueue1();
return 0;
}
Original: https://blog.csdn.net/weixin_72060925/article/details/127769927
Author: Turing_Sheep
Title: 第六章 队列的讲解与实现
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/654016/
转载文章受原作者版权保护。转载请注明原作者出处！