队列

发表于

队列是一种先进先出（First In First Out）的线性表，简称 FIFO 。允许插入的一端称为队尾，允许删除的一端称为队头。

假设队列是 q=（a1，a2，……,an），那么 a1 就是队头元素，而 an 就是队尾元素。

队列的一般操作有：

InitQueue(*Q)：初始化操作，建立一个空队列 Q。

DestoryQueue(*Q)： 若队列 Q 存在，则销毁它。

ClearQueue(*Q)：将队列 Q 清空。

QueueEmpty(Q)：若队列 Q 为空，返回 true，否则返回 false。

GetHead(Q,*e)：若队列 Q 存在且非空，用 e 返回队列 Q 的队头元素。

EnQueue(*Q，e)：若队列 Q 存在，插入新元素 e 到队列 Q 中并成为队尾元素，并用 e 返回其值。

DeQueue(*Q,*e)：删除队列 Q 中队头元素，并用 e 返回其值。

QueueLength(Q)：返回队列 Q 的元素个数。

循环队列

定义：我们把队列的这种头尾相接的顺序存储结构称为循环队列。

循环队列的顺序存储结构：

1
2
3
4
5
6
7
8
typedef int QElemType;	/* QElemType 类型根据实际情况而定，这里假设为 int */
/* 循环队列的顺序存储结构 */
typedef struct
{
	QElemType data[MAXSIZE];
	int front;		/* 头指针 */
	int rear;		/* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}sqQueue;

当队列为空时，头指针和尾指针都指向下标为 0 的位置。

由于队满是 front = rear，所以我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。队列满的条件是 (rear + 1) % QueueSize == front

循环队列初始化：

1
2
3
4
5
6
7
/* 初始化一个空队列 */
Status InitQueue(SqQueue *Q)
{
	Q->front = 0;
	Q->rear = 0;
	return OK;
}