By

本章我们主要介绍一下队列的实现。

1. 队列

和栈相反，队列（queue)是一种先进先出(first in first out,简称FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的。最早进队列的元素最早离开。在队列中，允许插入的一端叫做队尾（rear），允许删除的一端称为队头(front)。假设队列为q=(a1,a2,…,an)，那么a1就是队头元素，an就是队尾元素。队列中的元素是按照a1,a2,…,an的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在a1,a2,…, an-1都离开队列之后，an才能退出队列。

2. 链式队列

和线性表类似，队列也可以有两种存储表示。用链表表示的队列简称为链队列，如下图（左）所示。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了操作方便，我们也给链队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判决条件为头指针和尾指针均指向头结点，如下图（右(a))所示。

ds-link-queue

链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针，如上图（右(b)~(d))展示了这两种操作进行时指针变化的情况。下面给出链队列的一个基本实现。

2.1 链队列数据结构

下面是链队列数据结构：

typedef struct QNode{
	QElemType data;
	struct QNOde *next;
}QNode, *QueuePtr;

typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

相应实现如下：

Status InitQueue(LinkQueue *Q)
{
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
	if(!Q->front)
		return OVERFLOW;
	
	Q->front->next = NULL;

	return OK;
}

Status Destroy(LinkQueue *Q)
{
	while(Q->front)
	{
		Q->rear = Q->front->next;
		free(Q->front);

		Q->front = Q->rear;
	}
}

Status EnQueue(LinkQueue *Q, QElemType e)
{
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if(!p)
		return OVERFLOW;

	p->data = e;
	p->next = NULL;
	Q->rear->next = p;
	Q->rear = p;

	return OK;
}

Status DeQueue(LinkQueue *Q, QElemType *e)
{
	if(Q->front == Q->rear)
		return ERROR;

	p = Q->front->next;
	*e = p->data;
	
	Q->front->next = p->next;
	if(Q->rear == p)
		Q->rear = Q->front;

	free(p);
	return OK;
}

3. 循环队列

和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。为了在C语言中描述方便起见，在此我们约定： 初始化建空队列时，令front=rear=0，每当插入新的队列尾元素时，尾指针增1; 每当删除队列头元素时，头指针增1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。如下图所示：

ds-queue

假设当前队列分配的最大空间为6，在当队列处于上图(d)的状态时不可再继续插入新的队尾元素，否则会因数组越界而遭致程序代码被破坏。然而，此时又不宜如顺序栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。一个较巧妙的办法是将顺序队列臆造为一个环状的空间，如下图所示：

ds-queue-example 我们称之为循环队列。指针和队列元素之间关系不变。

如下图（a）所示的循环队列中，队列头元素是J3，队列尾元素是J5,之后J6,J7和J8相继插入，则队列空间均被占满， 如下图（b）所示，此时Q->front=Q->rear； 反之，若J3,J4,J5相继从图(a)中删除，是队列呈“空”状态， 如下图(c)所示。此时也存在关系式Q->front = Q->rear，由此可见，只凭Q->front = Q->rear无法判别队列空间是“空”还是“满”。

ds-queue-cycle 这里可有两种处理方法：

  • 另设一个标志位以区别队列是空还是满；

  • 少用一个元素空间，约定“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列呈满状态的标志。

由上述分析可见，在C语言中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度； 若用户无法预估所用队列的最大长度，则宜采用链队列。

3.1 循环队列的实现

下面给出循环队列的一个简易实现：

#define MAXQSIZE	100

typedef struct{
	QElemType *base;
	int front;		//头指针，若队列不空，指向队列头元素
	int rear;	    //尾指针，若队列不空，指向队列尾元素的下一位置
}SqQueue;

Status InitQueue(SqQueue *Q)
{
	Q->base = (QElemType *)malloc(sizeof(QElemType)*MAXQSIZE);

	if(!Q->base)
		return OVERFLOW;

	Q->front = Q->rear = 0;
	return OK;
}

int QueueLength(SqQueue Q)
{
	return (Q->rear - Q->front + MAXQSIZE) % MAXQSIZE;
}

Status EnQueue(SqQueue *Q, QElemType e)
{
	if((Q->rear + 1) % MAXQSIZE == Q->front)
		return ERROR;

	Q->base[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXQSIZE;
	return OK;
}

Status DeQueue(SqQueue *Q, QElemType *e)
{
	if(Q->rear == Q->front)
		return ERROR;
	
	*e = Q->base[Q->front];
	Q->front = (Q->front +1) % MAXQSIZE;
	return OK;
}