队列的概念

什么是队列呢？我们先看下面的图：

我们可以理解成高速公路上的隧道，根据这个图的描述

我们把需入队的元素看作一辆车，把队列看作隧道，由此我们可以看出

队列的特点是只允许从一端进入，从另一端离开。

队列就是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出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，如果不为空返回false
void 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们的观看是我坚持下去的动力

在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！