队列ADT
头文件

#ifndef _Queue_h

struct QueueRecord;
typedef struct QueueRecord *Queue;

int IsEmpty( Queue Q );
int IsFull( Queue Q );
Queue CreateQueue( int MaxElements );
void DisposeQueue( 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;
}

int IsFull( Queue Q )
{
	return Q->Size == Q->Capacity;
}

Queue CreateQueue( int MaxElements )
{
	Queue Q;

	if( MaxElements < MinQueueSize )
		Error( "Queue size is too small!!!" );

	Q = malloc( sizeof( struct QueueRecord ) );
	if( Q == NULL )
		FatalError( "Out of sapce!!!" );
	
	Q->Array = malloc( sizeof( ElementType ) * MaxElements );
	if( Q->Array == NULL )
		FatalError( "Out of space!!!" );
	Q->Capacity = MaxElements;
	MakeEmpty( Q );

	return Q;
}

void MakeEmpty( Queue Q )
{
	Q->Size = 0;
	Q->Front = 1;
	Q->Rear = 0;
}

static 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;
	}
}

ElementType Front( Queue Q )
{
	ElemewntType TmpCell;

	if( IsEmpty( Q ) )
	{
		Error( "Empty queue!" );
		return 0;
	}
	else
	{
		return Q->Array[ Q->Front ];
	}
}

ElementType FrontAndDequeue( Queue Q )
{
	ElemewntType TmpCell;

	if( IsEmpty( Q ) )
	{
		Error( "Empty queue!" );
		return 0;
	}
	else
	{
		Q->Size--;
		TmpCell = Q->Array[ Q->Front ];
		Q->Front = Succ( Q->Rear, Q );
		return TmpCell;
	}
}