数据结构中的队列 ADT
1. 队列模型
队列的基本操作是Enqueue(入队)，它是在表的末端(rear)插入一个元素，还有Dequeue(出队)，它是删除(货返回)在表的开头(叫做队头(front))的元素。下图显示一个队列的抽象模型。
2.队列的数组实现
如同栈的情形一样，对于队列而言任何表的实现都是合法的。像栈一样，对于每一种操作，链表实现和数组实现都给出快速O(1)运行时间。下面讨论队列的数组实现。
对于每一个队列数据结构，保留一个数组Queue[ ]以及位置Front和Rear，它们代表列表的两端。还要记录实际存在与队列中的元素的个数Size。所有这些信息是一个结构的一部分，除队列例程本身外通常不会有例程直接访问它们。下图表示处于某个中间状态的一个队列。顺便指出，图中那些空白单元是有着不确定的值的。特别地，前三个单元含有曾经属于该队列的元素。
操作应该是清楚地。为使一个元素X入队，让Size和Rear增1，然后置Queue[Rear] = X。若使一个元素出队，置返回值为Queue[Front]，Size减1，然后使Front增1。也可以有其他的策略。现在讨论错误的检测。
这种实现存在一个潜在的问题。经过10次入队后，队列似乎是满了，因为Rear现在是10，而下一次再入队就会是一个不存在的设置。然而，队列中也许只存在几个元素，因为若干元素可能已经出队了。像栈一样，即使在有许多操作的情况下队列也常常不是很大。
简单的解决方法是，只要Front或Rear到达数组的尾端，它就又绕回到开头。下图显示在某些操作期间的队列情况。这叫做循环数组(cicular array)实现。
现实回绕所需要的附加代码时极小的(虽然它可能使得运行时间加倍)。如果Front或Rear增1使得超越了数组，那么其值就要重置为数组的第一个位置。
关于队列的循环实现，有两件事情要警惕。第一，检测队列是否为空是很重要的，因为当队列为空时一次Dequeue操作将不知不觉 地返回一个不确定的值。第二，某些程序设计人员使用不同的方法来表示队列的队头的队尾。例如，有些人并不用一个单元来表示队列的大小，因为它们依靠的是基准情形，即当队列为空时Rear = Front -1.队列的大小是通过比较Rear和Front隐式算出的。这是一种非常隐秘的方法，因为存在某些特殊的情形，因此，如果你需要修改用这种方式编写的代码，那么你就要特别仔细。如果队列的大小不是结构的一部分，那么若数组的大小为ASize，则当存在ASize-1个元素时队列就满了，因为只有ASize个不同的大小值可被区分，而0是其中的一个。采用任意一种你喜欢的风格，但要确保你的所有里程都是一致的。由于实现方法有多种选择，因此如果你不使用表示大小的域，那就很可能有必要进行一些讨论，否则会在一个程序中使用两种选择。
在保证Enqueue的次数不会大于队列的大小的应用中，使用回绕是没有必要的。向栈一样，除非主调例程肯定队列为空，否则Dequeue很少执行。因此对这种操作，只要不是关键的代码，错误的调用常常被跳过。一般来说这并不是无可非议的，因为你可能得到的时间节省量是极小的。
通常编写某些队列的例程来结束本节。首先在给出队列的声明。正如对栈的数组实现所做的那样，添加一个最大大小的域。还需要提供例程CreatQueue和DisposeQueue。此外，还要提供测试一个队列是否为空的例程以及构造一个空队列的例程。可以编写函数IsFull，它完成其名字所指处的功能。注意，Rear在Front之前与初始化为1。将要编写的最后的操作是Enqueue例程。严格遵循上面的描述，实现代码如下所示：
队列类型的声明：
# ifndef _Queue_h
struct QueueRecord;
typedef struct QueueRecord *Queue;
int IsEmpty(Queue Q);
int IsFull(Queue Q);
Queue CreateQueue( int MaxElements );
void DisposedQueue(Queue Q);
void MakeEmpty( Queue Q );
void Enqueue( ElementType X, Queue Q );
ElementType Front( Queue Q );
void Dequeue( Queue Q );
ElementType FrontAndDequeue( Queue Q );
#endif /*_Queue_h*/
/* Place in implementation file */
/* Queue implementation is a dynamically allocated array */
# define MinQueueSize( 5 )
struct QueueRecord
{
int Capacity;
int Front;
int Rear;
int Size;
ElementType *Array;
};测试队列是否为空的例程------数组实现：
int
IsEmpty( Queue Q )
{
return Q->Size == 0;
}构造空队列的例程------数组实现：
void
MakeEmpty( Queue Q )
{
Q->Size = 0;
Q->Front = 1;
Q->Rear = 0;
};入队的例程------数组实现：
satic int
Succ( int Value, Queue Q )
{
if( ++Value == Q->Capacity )
Value - 0;
return Value;
}
void
Enqueue( ElementType X, Queue Q )
{
if( IsFull( Q ) )
Error("Full queue"):
else
{
Q->Size++;
Q->Rear = Succ( Q-Rear, Q );
Q->Array[ Q-Rear ] = X;
}
}