队列

一、概念

队列是运算受限的线性表，插入操作在队尾进行，而删除操作在队头进行，又称为先进先出的线性表。

• 队头：只允许进行删除操作的一端
• 队尾：只允许进行插入的一端

二、顺序队列

顺序队列是指利用一组连续的存储单元（一维数组），依次存放从队首到队尾的各个元素，称为顺序队列，并附设两个指针，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置（可能定义不同）。

#define MaxSize 100
typedef struct{
	Elemtype data[MaxSize];
	int front,rear;
} SqQueue;

• 队空：
• 进队：若队不满，先送值进队尾元素，再将队尾指针加1
• 出队：若队不空，先取队头元素，再将队头指针加1

TIP

栈和队列的判空、判满条件会根据实际条件不同而变化

存在的问题：顺序队列中存在“假溢出”现象。因为在入队和出队操作中，头、尾指针只增加不减少，致使被删除元素的空间永远无法重新利用。

循环队列

为了克服顺序队列假溢出的缺点，将为队列分配的空间看作一个首尾相接的圆环，并称这种队列为循环队列。在循环队列中进行出队、入队操作时，队首、队尾指针仍要加1，向前移动。只不过当指向上界MaxSize-1时，再前进一个位置就自动到0，这可以用取余运算实现。

• 队空：
• 队满：
• 队列长度：

区分队空和队满：

• 一般牺牲一个单元来区分，则队头指针在队尾指针的下一个位置为队满标志
• 类中增设表示元素个数的成员变量

三、链式队列

链式队列实际上是同时带有队头和队尾指针的单链表，限制在仅在表头进行删除操作和表尾进行插入操作。

• 队空：

• 链式队列适合数据变动较大的情形，不存在溢出问题

四、应用

1. 层序遍历

利用队列先进先出的特性，先把树的根节点入队，然后每出一次都把它的子节点入队，出子节点时也一样。

2. 缓冲区

主机和打印机速度不匹配时，若直接把输出的数据送给打印机显然是不行的。解决的方法是设置一个打印缓冲区，主机把要打印的数据依次写入到缓冲区，打印机则从缓冲区中按照先进先出的原则取出数据打印。

3. 资源竞争

在多终端系统中，有多个用户需要cpu运行自己的程序，操作系统按照每个请求时间上的先后顺序，把他们排成一个队列，每次把cpu分配给队首请求的用户使用。