初阶数据结构
第一章 时间复杂度和空间复杂度
第二章 动态顺序表的实现
第三章 单向链表的讲解与实现
第四章 带头双向链表的讲解与实现
第五章 栈的讲解与实现
第六章 队列的讲解与实现
前言
在上一章节中,我们了解到栈这种数据结构的特点是先进后出,那么今天所讲解的队列的特点则恰恰与之相反。队列这种数据结构的特点是:先进先出,后进后出。接下来我们将对其进行详细地讲解。
一、什么是队列?
队列在生活中是非常常见的,比如我们做核酸的时候,都会以队列的形式排队。很明显,先排队的人就可以先做核酸,后排队的人只能后做核酸。这其实就是队列这种结构的特点,那么其逻辑结构如下图所示:
二、队列的定义:
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;
}