队列-数组实现C

/* 异常处理头文件 */
/* fatal.h */
#include <stdio.h>
#include <stdlib.h>

#define Error( Str ) FatalError( Str )
#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 )

/* queue.h */
typedef int ElementType;
#ifndef _Queue_h
#define _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.c */
#include "queue.h"
#include "fatal.h"
#include <stdlib.h>

#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 space!!!" );

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

void
DisposeQueue( Queue Q )
{
  if( Q != NULL )
    {
      free( Q->Array );
      free( Q );
    }
}

/* 保证不越界 */
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 )
{
  if( !IsEmpty( Q ) )
    return Q->Array[ Q->Front ];
  Error( "Empty Queue" );
  return 0;
}

void
Dequeue( Queue Q )
{
  if( IsEmpty( Q ) )
    Error( "Empty queue" );
  else
    {
      Q->Size--;
      Q->Front = Succ( Q->Front, Q );
    }
}

ElementType
FrontAndDequeue( Queue Q )
{
  ElementType X = 0;
  
  if( IsEmpty( Q ) )
    Error( "Empty queue" );
  else
    {
      Q->Size--;
      X = Q->Array[ Q->Front ];
      Q->Front = Succ( Q->Front, Q );
    }
  return X;
}

/* testque.c */
#include <stdio.h>
#include "queue.h"

int
main()
{
  Queue Q;
  int i;

  Q = CreateQueue( 12 );

  for( i = 0; i < 10; i++ )
    Enqueue( i, Q );

  while ( !IsEmpty( Q ) )
    {
      printf( "%d\n", Front( Q ) );
      Dequeue( Q );
    }

  for( i = 0; i < 10; i++ )
    Enqueue( i, Q );

  while ( !IsEmpty( Q ) )
    {
      printf( "%d\n", Front( Q ) );
      Dequeue( Q );
    }

  DisposeQueue( Q );
  return 0;
}