本章重点

• 队列的概念及结构
  
• 队列的实现方式
  
• 链表方式实现栈接口
  
• 队列面试题
  

一、队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

• 队头：线性表允许删除的那一端。
• 队尾：线性表允许插入的那一端。
• 空队：不含任何元素的空表。

二、队列的实现方式

       如图3-5所示为依次向队列中插入元素 a0，a1，…，an-1后的示意图，其中，a0是当前队头元素，an-1 是当前队尾元素。

 就像在食堂买饭就餐一样，如果你在就餐人不多时去食堂就餐，你一到买饭窗口就能得到食堂服务人员的服务；但如果你在就餐人很多时去食堂就餐，你就需要在某个窗口排队等待，直到轮到你时才能得到食堂服务人员的服务。在软件设计中也经常会遇到需要排队等待服务的问题。队列可用于临时存储那些需要等待接受服务的信息序列。

       队列只允许在头部插入，尾部删除，因此队列的实现一般可以使用数组或者链表实现。

1.顺序队列

如图3-6所示为一个有6个内存单元的顺序队列的动态示意图，图中front为队头指针，rear为队尾指针。图3-6 (a)表示一个空队列；图3-6 (b)表示A、B、C入队列后的状态；图3-6 (c) 为A、B出队列后的状态；图3-6 (d) 为D，E入队列后的状态。

2.链式队列

我们已知，队列是操作受限制的线性表，队列有队头和队尾，插入元素的一端称为队尾,删除元素的一端称为队头。

链式队列的队头指针指向队列的当前头结点位置，队尾指针指向队列的当前队尾结点位置。对于不带头结点的链式队列，出队列时可直接删除队头指针所指的结点，因此链式队列没有头结点更方便。一个不带头结点、队列中有元素a0，a1，…，an-1的链式队列的结构如图3-9所示，其中，指针 front 指示的是链式队列的队头结点，指针 rear 指示的是链式队列的队尾结点。

三、链表方式实现栈接口

由于队列只允许在头部插入，尾部删除，因此我们会改变头结点，前面我们学过用二级指针和返回值两种方式来处理头结点改变，今天我们来学一种新方式：结构体修改，将队列的头结点和尾结点放入到一个结构体当中，通过结构体地址就可以修改结构体的内容，同时还加入了一个size，用来计算当前队列的长度。

typedef int QDataType;
// 单链式结构：表示队列
typedef struct QListNode
{
  struct QListNode* Next;
  QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
  QNode* front;
  QNode* rear;
  int size;
}Queue;
// 初始化队列
void QueueInit(Queue * q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

1.初始化队列：void QueueInit(Queue* q)

直接将front和rear域都设置为NULL，将队列长度设置为0，

// 初始化队列
void QueueInit(Queue* q)
{
  assert(q);
  q->front = q->rear = NULL;
  q->size = 0;
}

2.队尾入队列：void QueuePush(Queue* q, QDataType data)

构造一个节点newnode，data域存储数据，next域存储NULL，若原链队为空，则将链队结点的两个域都指向结点newnode，否则将结点newnode链接到单链表末尾，并让链队结点的rear域指向它，再让队列的长度+1

// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = data;
  newnode->Next = NULL;
  if (q->rear == NULL)
  {
    q->front = q->rear = newnode;
  }
  else
  {
    q->rear->Next = newnode;
    q->rear = newnode;
  }
  q->size++;
}

3.队头出队列：void QueuePop(Queue* q)

若原链队为空，则下溢，assert断言提示错误，否则将队首结点的Next域赋值给next，并删除队首结点，若原链队只有一个结点，则需要将链队结点的两个域都设置为NULL，表示此时链队已空。然后队列长度-1.

// 队头出队列
void QueuePop(Queue* q)
{
  assert(q);
  //队列为空,断言
  assert(!QueueEmpty(q));
  //rear出现野指针的问题
  if (q->front->Next == NULL)
  {
    free(q->front);
    q->front = q->rear = NULL;
  }
  else
  {
    QNode* next = q->front->Next;
    free(q->front);
    q->front = next;
  }
  q->size--;
}

4.获取队列头部元素：QDataType QueueFront(Queue* q)

// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
  assert(q);
  //队列为空,断言
  assert(!QueueEmpty(q));
  return q->front->data;
}

5.获取队列队尾元素：QDataType QueueBack(Queue* q)

// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
  assert(q);
  //队列为空,断言
  assert(!QueueEmpty(q));
  return q->rear->data;
}

6.获取队列中有效元素个数：int QueueSize(Queue* q)

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

7.检测队列是否为空：bool QueueEmpty(Queue* q)

// 检测队列是否为空
bool QueueEmpty(Queue* q)
{
  assert(q);
  //头为空，该队列就为空
  //返回true - 队列就为空
  //返回false - 队列不为空
  return q->front == NULL;
}

8.销毁队列：void QueueDestroy(Queue* q)

销毁队列创建一个结点保存下个结点的值，释放当前结点，然后依次遍历队列，依次释放结点。释放后需要将队头和队尾都置空，队列长度设置为0，由于是通过结构体去修改头结点，此时队列已经为空指针，在调用函数后，不需要手动将头指针置空。

// 销毁队列
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->front;
  while (cur)
  {
    QNode* next = cur->Next;
    free(cur);
    cur = next;
  }
  q->front = q->rear = NULL;
  q->size = 0;
}

【排排站：探索数据结构中的队列奇象】（下）：https://developer.aliyun.com/article/1424896