队列

  • 队列的概念
  • 队列的实现过程
  • 队列的结构体与接口函数的定义
  • 队列的接口实现
    • ①初始化队列(QueueInit)
    • ②队尾入队列(QueuePush)
    • ③队头出队列(QueuePop)
    • ④队头元素(QueueFront)
    • ⑤队尾元素(QueueBack)
    • ⑥有效元素个数(QueueSize)
    • ⑦检测队列是否为空(QueueEmpty)
    • ⑧销毁队列(QueueDestroy)
  • 结语

队列的概念

什么是队列呢?我们先看下面的图:

我们可以理解成高速公路上的隧道,根据这个图的描述
我们把需入队的元素看作一辆车,把队列看作隧道,由此我们可以看出
队列的特点是只允许从一端进入,从另一端离开。
队列就是只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头

关于队列的相关名词:

入队:进入队列,即向队列中插入元素
出队:离开队列,即从队列中删除元素
队头:允许出队(删除)的一端
队尾:允许入队(插入)的一端
队头元素:队列中最先入栈的元素
队尾元素:队列中最后入栈的元素

我们可以直接将队头元素看作队头,队尾元素看作队尾。

队列的实现过程

和栈一样,队列也可以有两种实现方式:数组实现的顺序队列和链表实现的链队列,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
1.数组实现队列
数组队列的实现主要有以下两个缺点
内存浪费:用于存储队列元素的数组空间永远不能用于存储该队列的元素,因为元素只能在前端插入,并且 front 的值可能很高,以至于, 在那之前的所有空间,永远无法填满。
数组大小:在某些情况下,如果我们使用数组来实现队列,可能需要扩展队列以插入更多元素,扩展数组大小几乎是不可能的,因此确定正确的数组大小总是一个 队列的数组实现中的问题。
因此在这我们不详细介绍,主要介绍链表实现队列的形式。
2.链表实现队列
链表实现的队列形式我们主要用图的形式来表现,看下图:

队列的结构体与接口函数的定义

队列的结构体定义
代码如下:

typedef int QDataType;typedef struct QueueNode{struct QueueNode* next;QDataType data;}QueueNode;typedef struct Queue{QueueNode* head;QueueNode* tail;}Queue;

这里我们使用两个结构体嵌套,QueueNode包含了元素和下一级指针,Queue则在QueueNode基础上嵌套了头指针和尾指针记录入队和出队的操作。
队列的接口函数定义
代码如下:

void QueueInit(Queue* pq);// 初始化队列void QueuePush(Queue* pq, QDataType x);// 队尾入队列void QueuePop(Queue* pq);// 队头出队列QDataType QueueFront(Queue* pq);// 获取队列队头元素QDataType QueueBack(Queue* pq);// 获取队列队尾元素int QueueSize(Queue* pq);// 获取队列中有效元素个数bool QueueEmpty(Queue* pq);// 检测队列是否为空,如果为空返回ture,如果不为空返回falsevoid QueueDestroy(Queue* pq);// 销毁队列

接下来我们就将这几个接口函数来一一实现。

队列的接口实现

①初始化队列(QueueInit)

代码如下:

void QueueInit(Queue* pq){assert(pq);pq->head = NULL;pq->tail = NULL;}

初始化没什么好讲的,就是头尾为空就ok。

②队尾入队列(QueuePush)

代码如下:

void QueuePush(Queue* pq, QDataType x){assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}

首先使用malloc函数动态分配内存,将x赋给newnode的data,下一级指针指向空,
下面分两种情况讨论,第一种是队列为空时,将newnode这个临时结点直接赋给头指针和尾指针,第二种情况是已经有元素的情况下,就将newnode赋给尾结点的next,再将尾指针指向新的结点,完成尾插操作

③队头出队列(QueuePop)

代码如下:

void QueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));//断言队列不为空QueueNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}}

这里的断言在下面的代码会实现,首先我们要将队头的下一结点赋给临时结点next,
然后释放掉头队头内存空间,再把临时结点next赋给新的队头指针,再考虑删完的情况下,把队尾结点也置空,完成出队操作。

④队头元素(QueueFront)

代码如下:

QDataType QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));//断言队列不为空return pq->head->data;}

同样断言不为空,然后直接返回头指针的data元素即可。

⑤队尾元素(QueueBack)

代码如下:

QDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}

队尾元素也和上面一样,首先断言队列不为空,再直接返回队尾指针的data元素即可。

⑥有效元素个数(QueueSize)

代码如下:

int QueueSize(Queue* pq){assert(pq);int n = 0;QueueNode* cur = pq->head;while (cur){++n;cur = cur->next;}return n;}

这里我们创建一个临时结点cur,将队头结点赋给它,然后利用while循环对队列进行遍历,临时变量n进行记录,最后返回n的值即为有效元素个数。

⑦检测队列是否为空(QueueEmpty)

代码如下:

bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}

和前面的栈的接口函数一样,这个函数返回类型可以是int,这里我使用bool类型也是一样的,只不过我这返回的是逻辑值true或是false,如果为空返回ture,如果不为空返回false。

⑧销毁队列(QueueDestroy)

代码如下:

void QueueDestroy(Queue* pq){assert(pq);QueueNode* cur = pq->head;while (cur != NULL){QueueNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}

销毁队列的实现和链表是一样的(本来这里的队列就是用链表实现的),首先将队头结点指针赋给临时结点cur,然后遍历每个队列结点,一个一个释放内存空间,最后将队头结点和队尾结点指向空,完成销毁链表操作。

结语

扩展:,实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现,也可以使用循环链表实现。这里我们就不讲这么多啦,如果大家有兴趣的话,作者可以单独写一篇博客来讲一讲。

制作不易,如有不正之处敬请指出
感谢大家的来访,UU们的观看是我坚持下去的动力
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!