队列也是一种简单却很有用的数据结构,其特点是先进先出,基本操作是enqueue(入列)和dequeue(出列)
下面给出数组实现的代码:
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED
struct QueueRecord;
typedef struct QueueRecord * Queue;
typedef double ElementType;
int IsEmpty(Queue Q);
int IsFull(Queue Q);
Queue CreatQueue(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_INCLUDED
实现:
#include "Queue.h"
#include <stdlib.h>
/* Queue implementation is a dynamically allocated array */
/* 用一个动态数组来实现队列 */
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;
}
Queue CreatQueue(int MaxElements)
{
Queue queue = malloc(sizeof(struct QueueRecord));
queue->Array = malloc(sizeof(ElementType)*MaxElements);
if(queue == NULL || queue->Array == NULL)
FatalError("Something Error");
queue->Capacity = MaxElements;
MakeEmpty(queue);
}
static int Succ(int value,Queue Q)
{
if(++value == Q->Capacity)
value = 0;
return value;
}
void Enqueue(ElementType X,Queue Q)
{
if( IsFull( Q ) )
FatalError("Full queue");
else
{
Q->Size++;
Q->Rear = Succ(Q->Rear,Q);
Q->Array[ Q->Rear ] = X;
}
}
int IsFull(Queue Q)
{
return Q->Size == Q->Capacity;
}
void Dequeue(Queue Q)
{
if(IsEmpty(Q))
FatalError("Empty queue");
else
{
Q->Size--;
Q->Front = Succ(Q->Front,Q);
}
}
ElementType FrontAndDequeue(Queue Q)
{
ElementType Tmp;
if(IsEmpty(Q))
Error("Empty queue");
else
{
Q->Size--;
Tmp = Q->Array[Q->Front];
Q->Front = Succ(Q->Front,Q);
return Tmp;
}
}
void DisposeQueue( Queue Q )
{
free(Q->Array);
free(Q);
}
void Error(char * error)
{
printf("%s",error);
}
void FatalError(char * fatalerror)
{
printf("%s",fatalerror);
return 0;
}
int main()
{
Queue q = CreatQueue(200);
int i;
for(i = 1; i <= 110; i++)
Enqueue(i,q);
for(i = 1;i <=100; i++)
printf("%lf\n",FrontAndDequeue(q));
return 0;
}
同样的,在最后加上了main函数用于测试。测试结果如下图:
注:代码改编自《数据结构与算法分析:C语言描述》第二版