队列

一、队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表；队列中的数据元素遵守先进先出FIFO（First In First Out）的原则；

入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头。

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表；队列中的数据元素遵守先进先出FIFO（First In First Out）的原则；

入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头。

A 从队尾插入一个新元素

B 从队列中删除第i个元素

C 判断一个队列是否为空

D 读取队头元素的值

答案：B 队列只能删除队头的数据。

二、队列的实现

1、队列的结构

和栈一样，队列既可以使用顺序表实现，也可以使用链表实现，这里我们使用单链表实现，原因如下：

1、队列需要删除头部的元素，单链表头删的效率为O(1)；

2、使用链表可以按需申请空间，避免了空间的浪费；

但是我们发现使用单链表实现队列存在一个问题，那就是单链表尾插以及计算链表长度的效率都为O(N)，不符合我们的预期，那么我们需要把单链表改造为循环链表吗？可以是可以，但是这样又把队列的结构搞复杂了；所以综合考虑，这里我们增加三个变量，一个用于记录队尾，一个用于记录队头，还有一个用于记录队列的长度。

结构的定义

//符号和结构的定义
typedef int QEDataType;
typedef struct QueueNode  //队列的一个节点
{
  QEDataType data;
  struct QueueNode* next;
}QENode;
typedef struct Queue  //队列
{
  QENode* head;  //记录队列的头
  QENode* tail;  //记录队列的尾
  int size;      //记录队列的长度
}Queue;

2、初始化队列

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

3、从队尾入队列

由于我们使用了一个结构体来记录队列的头和尾，那么这里我们改变队列的头和尾时只需要改变结构体即可，所以只需要传递一级指针；

另外，队列也只能从队尾入数据，所以我们也没有必要单独封装一个 BuyNode 函数。

//队尾入队列
void QueuePush(Queue* pq, QEDataType x)
{
  assert(pq);
  //创建一个新节点
  QENode* newnode = (QENode*)malloc(sizeof(QENode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  //当入第一个元素时，需要改变队列的头
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = pq->tail->next;
  }
  pq->size++;
}

4、从队头出队列

这里我们除了正常的对队列进行判空之外，还有一个需要特别注意的地方：当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，会形成野指针，所以我们这里需要单独判断。

//队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  //当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，形成野指针，所以我们这里要单独判断
  if (pq->head == pq->tail)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QENode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
  pq->size--;
}

5、获取队头元素

//返回队头元素
QEDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}

6、获取队尾元素

//返回队尾元素
QEDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

7、获取队列长度

//返回队列长度
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

8、判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

9、销毁队列

//销毁队列
void QueueDestory(Queue* pq)
{
  assert(pq);
  QENode* cur = pq->head;
  while (cur)
  {
    QENode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}

注意：和栈一样，队列也不需要定义 print 函数，因为队列也不能遍历，要想取出队头后面的元素，我们必须先 pop 掉之前的元素，让该元素成为队头。

三、完整代码

1、Queue.h

#pragma once    //防止头文件重复包含
//头文件的包含
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//符号和结构的定义
typedef int QEDataType;
typedef struct QueueNode  //队列的一个节点
{
  QEDataType data;
  struct QueueNode* next;
}QENode;
typedef struct Queue  //队列
{
  QENode* head;  //记录队列的头
  QENode* tail;  //记录队列的尾
  int size;      //记录队列的长度
}Queue;
//函数的声明
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QEDataType x);
//队头出队列
void QueuePop(Queue* pq);
//返回队头元素
QEDataType QueueFront(Queue* pq);
//返回队尾元素
QEDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//返回队列长度
int QueueSize(Queue* pq);

2、Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
//初始化队列
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
//销毁队列
void QueueDestory(Queue* pq)
{
  assert(pq);
  QENode* cur = pq->head;
  while (cur)
  {
    QENode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
//队尾入队列
void QueuePush(Queue* pq, QEDataType x)
{
  assert(pq);
  //创建一个新节点
  QENode* newnode = (QENode*)malloc(sizeof(QENode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  //当入第一个元素时，需要改变队列的头
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = pq->tail->next;
  }
  pq->size++;
}
//队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  //当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，形成野指针，所以我们这里要单独判断
  if (pq->head == pq->tail)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QENode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
  pq->size--;
}
//返回队头元素
QEDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
//返回队尾元素
QEDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
//返回队列长度
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

3、test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
int main()
{
  Queue q;
  //初始化队列
  QueueInit(&q);
  //队尾入队列
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  //队列也不能遍历，取出一个元素即代表从队头出一个元素
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  //销毁队列
  QueueDestory(&q);
  return 0;
}

大家也可以去我的 Gitee 仓库中获取完整代码：Queue/Queue · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)

【数据结构】栈和队列(2)

队列