# 队列

# 1. 概念

队列是只允许在一端删除，另一端插入的线性表，允许删除的一端叫队头 (front),

允许插入的一端叫队尾 (rear)。

特点：先进先出 (FIFO)

1. 语言描述

	#define MAXSIZE 1024 // 最大队列长度
	typedef struct
	{
	datatype data[MAXSIZE]; /* 队员的存储空间 */
	int rear,front; /* 队头队尾指针 */
	}SqQueue;

2. 具体操作

	置空队: sq.front= sq.rear=0
	入队: sq.data[sq.rear]=x; sq.rear++;
	出队: x=sq.data[sq.front] sq.front++;
	读队头、队尾: sq.data[sq.front] sq.data[sq.rear-1]
	队中元素个数:m=sq.rear-sq.front
	队满:m==MAXSIZE
	队空:m==0

3. 顺序队列的假溢出

如图 (无图) 所示的状态，不能再继续插入新的队尾元素，否则会因为数组越界导致程序代码被破坏。而此时又不宜如顺序栈那样，进行存储空间再分配来扩大数组的空间，因为队列的实际可用空间并未占满，这种情况叫做顺序队列的假溢出。

解决方案：

① 队首固定，每次出队剩余元素向下移动 —— 浪费时间。
② 循环队列。