【初阶数据结构与算法】线性表之队列的定义与实现

一、队列的概念与结构

1. 概念

   队列是一种只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，它具有先进先出FIFO（后进后出）的特性
   用来插入数据的那一端称为队尾，用来删除数据的一端则称为对头，插入数据被称为入队列，删除数据被称为出队列，队列的大致示意图如下：

   队列的数据从队尾插入，从队头删除，根据上图的示意，我们就可以发现，A先进入队列，B后进入队列，那么在出队的时候，就还是A先出，B后出，所以队列确实满足先进先出，后进后出的特性

2.队列结构定义

   队列和栈一样既可以选择数组做底层，也可以选择链表作为它的底层，那么哪一个更好呢？这个就需要我们去分析一下了
   如果采用数组，那么我们入队列就可以直接在数组最后添加数据，时间复杂度为O(1)，比较方便，但是当我们要从数组头删数据就比较麻烦了，因为数组头删的时间复杂度为O(N),效率并不是很高
   我们再来分析一下使用链表怎么样，如果我们使用链表实现队列，那么在头部删除没有问题了，时间复杂度为O(1)，但是我们要在最后插入数据，对于链表来说，尾插的时间复杂度是O(N)，那么到底选哪一个才好？
   这里就不卖关子了，我们队列这个结构最好使用链表完成，我们要知道为什么链表尾插的时间复杂度为O(N)，因为我们找不到尾结点，需要循环遍历链表找到尾结点才能尾插，那么我们能不能想办法直接找到尾结点呢
   当然可以，链表不好的地方就是不方便找尾结点，既然知道了不足，我们在定义队列时就可以这样定义：让队列里面包含两个指针，分别指向链表的头和尾节点，反正队列只需要操作队头和队尾的数据
   我们拿到队尾和队头的节点后基本上就可以完成队列的操作了，其它节点我们并不关心，但是由于队列是建立在链表结构之上，所以我们要先定义一个类似于链表节点的队列节点结构，然后才能让队列指向它的头和尾，具体结构如下：

typedef int QDataType;//队列中一个节点的定义
//看起来和链表差不多
//但是要注意这里它已经变成队列的节点了
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;//真正使用的对列的定义
typedef struct Queue
{//指向队头的指针QueueNode* phead;//指向队尾的指针QueueNode* ptail;
}Queue;

   在上面的队列结构里，只有两个指向队列头和尾的指针，整个队列的操作就可以基本上只通过这两个指针来操作了，我们队列节点就是仿造链表节点来进行定义的，所以可以说我们队列的底层结构还是链表，只是对它进行封装后就变成了我们的队列
   那么这样的结构是否完美了呢？既然我们要实现一个队列，就应该尽可能的想到它的更多应用场景，如果我们需要计算这个队列的长度，是不是就会很麻烦，又要遍历整个队列才能得出结果，时间复杂度为O(N)
   所以为了优化这一点，在队列结构中做了优化，我们加入了一个新的成员，它用来记录队列的长度，而队列节点结构的定义不变，如下：

typedef int QDataType;//队列一个节点的定义
typedef struct QueueNode
{QueueDataType data;struct QueueNode* next;
}QueueNode;//真正使用的对列的定义
typedef struct Queue
{//用来记录队列的长度int size; //指向队头的指针QueueNode* phead;//指向队尾的指针QueueNode* ptail;
}Queue;

   如果对链表还不熟悉的话，推荐先学习链表：【初阶数据结构与算法】线性表之单链表的定义与实现

二、队列的实现

1.队列的初始化和销毁

初始化

   队列里面保存的是指向队头和队尾的指针，以及保存队列的长度的size，分别置空即可，如下：

//队列初始化
void QueueInit(Queue* pq)
{assert(pq);pq->size = 0;pq->phead = pq->ptail = NULL;
}

销毁

   队列的销毁也很简单，只需要通过队列中存储的头指针，遍历销毁整个队列即可，最后将存储的指针和队列大小置空，如下：

//队列销毁
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* del = pcur;pcur = pcur->next;free(del);}pq->phead = pq->ptail = NULL;pq->size = 0;
}

2.队列的节点申请和入队列操作

队列的节点申请

   由于我们入队列必须要申请节点，所以我们将其封装为一个函数，队列的节点申请和链表的节点申请类似，直接malloc一个节点大小的空间出来，然后根据给出的数据简单初始化一下这个节点即可，但是不要忘记了判断malloc返回值，以免节点申请失败，如下：

//队列节点申请
QueueNode* QueueBuyNode(QDataType x)
{QueueNode* newnode = malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;return newnode;
}

入队列

   解决了队列节点的申请后，我们就可以直接来实现入队列的操作了，由于我们队列结构中已经有了尾结点的地址，所以我们可以直接让尾结点的next指针指向新节点，然后让队列中保存的尾结点更新一下
   但是我们要注意一下，我们在第一次入队列时，队列为空，那么尾结点自然也就不存在，此时按照上面的步骤去操作就要出错，所以我们最好判断一下，如果队列为空，直接让头和尾指向新节点，让size++，否则就按照上面的逻辑走，如下：

//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = QueueBuyNode(x);if (pq->phead = NULL){pq->phead = pq->ptail = newnode;pq->size++;return;}pq->ptail->next = newnode;pq->ptail = newnode;pq->size++;
}

3.队列的判空和出队列操作

队列的判空

   我们要出队列就一定要保证队列中有数据，所以我们先来实现队列的判空，队列的判空也非常简单，只需要判断队列中的phead是否为空即可，如下：

//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

出队列

   有了队列判空之后，我们就可以在出队列前判断一下队列是否为空，不为空我们才继续进行出队列操作，我们之前说过，出队列是在删除队列的头
   由于我们队列结构中有队列的头，所以删除队列的头结点也很简单，可以先创建一个队列节点来保存头结点的下一个节点，然后直接释放掉头结点，释放掉之后让pq中的头指针重新指向保存的节点
   当然，出队列说明队列的有效节点个数要少一个了，所以不要忘了让size- -，如下：

//出队列
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;pq->size--;
}

4.取队头和队尾元素

取队头元素

   取队头元素就是取出队列中第一个元素，直接返回phead中的元素即可，如下：

//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);return pq->phead->data;
}

取队尾元素

   取队尾元素就是取出队列中最后一个元素，直接返回ptail中的元素即可，如下：

//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);return pq->ptail->data;
}

5.获取队列有效节点个数

   我们队列有效元素个数一直是size在记录，直接将其返回就可以了，如下：

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

三、队列源码

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int QDataType;//队列一个节点的定义
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;//真正使用的对列的定义
typedef struct Queue
{int size;QueueNode* phead;QueueNode* ptail;
}Queue;//队列初始化
void QueueInit(Queue* pq)
{assert(pq);pq->size = 0;pq->phead = pq->ptail = NULL;
}//队列销毁
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* del = pcur;pcur = pcur->next;free(del);}pq->phead = pq->ptail = NULL;pq->size = 0;
}//队列节点申请
QueueNode* QueueBuyNode(QDataType x)
{QueueNode* newnode = malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = QueueBuyNode(x);if (pq->phead == NULL){pq->phead = pq->ptail = newnode;pq->size++;return;}pq->ptail->next = newnode;pq->ptail = newnode;pq->size++;
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//出队列
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;pq->size--;
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);return pq->ptail->data;
}//获取队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

   那么今天关于队列的定义和实现就分享到这里，有什么疑问欢迎提出，下一篇我将会带大家做几道关于栈和队列的练习，随后就进入二叉树的学习，小小期待一下吧！
   bye~