队列

基本概念

先进先出（FIFO, First-In-First-Out）的线性表
在具体应用中通常用链表或者数组来实现
队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作

单链队列

使用链表作为基本数据结果，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高

/* 单链队列——队列的链式存储结构 */
typedef struct QNode
{
  QElemType data;
  struct QNode *next;
}QNode,*QueuePtr;

循环队列

循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

/* 队列的顺序存储结构(循环队列) */
#define MAX_QSIZE 5 /* 最大队列长度+1 */
typedef struct
{
  QElemType *base; /* 初始化的动态分配存储空间 */
  int front; /* 头指针，若队列不空，指向队列头元素 */
  int rear; /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;

假溢出

当队列满后，即便全部元素都出队，队列还是满的状态。这种情况就叫做“假溢出”，即数组中明明有可用空间，但却无法使用。