队列――链表与数组实现(数据结构与算法分析C语言版) (二)

#include "queue.h"
#include
#include

struct QNode
{
ElementType Element;
QNodePtr Next;
};

struct Node
{
QNodePtr Front;
QNodePtr Rear;
};

int IsEmpty( Queue Q )
{
return Q->Rear == Q->Front;
}

void MakeEmpty( Queue Q )
{
if (Q == NULL)
{
printf("The queue is empty! Must use CreateQueue first!\n");
return;
}
else
{
while(!IsEmpty(Q))
Dequeue(Q);
}
}

Queue CreateQueue()
{
//不仅要为对头(Queue)申请空间，还要为队列元素/节点（QNode）申请空间.
Queue Q;
Q = (Queue)malloc(sizeof(struct Node));
if (Q == NULL)
{
printf("Out of space!\n");
return NULL;
}
Q->Front = Q->Rear = (QNodePtr)malloc(sizeof(struct QNode));

if (Q->Front == NULL)
{
printf("Out of space!\n");
return NULL;
}
Q->Front->Next = NULL;
return Q;
}

void DisposeQueue( Queue Q )
{
while (Q->Front != NULL)
{
Q->Rear = Q->Front->Next;
free(Q->Front);
Q->Front = Q->Rear;
}
}

void Dequeue( Queue Q )
{
//删除链队列第一个元素
if (!IsEmpty(Q))
{
QNodePtr P;
P = Q->Front->Next;
Q->Front->Next = P->Next;
if (Q->Rear == P) //判断队列中是否只有一个元素
Q->Rear = Q->Front;
free(P);
}
else
{
printf("The queue is empty!\n");
}
}

void EnQueue( ElementType X, Queue Q )
{
QNodePtr P = (QNodePtr)malloc(sizeof(struct QNode));
if (P == NULL)
{
printf("Out of space!\n");
return;
}
else
{
P->Next = NULL;
P->Element = X;
Q->Rear->Next = P;
Q->Rear = P;
}
}

ElementType Front( Queue Q )
{
return Q->Front->Next->Element;
}

ElementType FrontAndDequeue( Queue Q )
{
ElementType X = 0;
if (!IsEmpty(Q))
{
X = Front(Q);
Dequeue(Q);
}
else
{
printf("The queue is empty!\n");
}
return X;
}

void PrintQueue( Queue Q )
{
QNodePtr P = Q->Front;
while (P != Q->Rear)
{
P = P->Next;
printf("%d\n", P->Element);
}
}循环队列一般是用循环数组实现，其判空条件有多种方式：其一是设一个标志位以区别队列是空还是满；其二是少用一个元素空间，约定以队列头指针在队列尾指针的下一位置上作为队列呈满状态标志。或者是如下面代码所示，为表示队列的结构体设置一个表示队列大小的size标志，若size为0，那么队列为空。
数组实现：队列头文件，queue.h

[cpp]
typedef int ElementType;

#ifndef _QUEUE_
#define _QUEUE_

struct QueueRecord;
typedef 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

typedef int ElementType;

#ifndef _QUEUE_
#define _QUEUE_

struct QueueRecord;
typedef 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.cpp

[cpp] view plaincopyprint #include "queue.h"
#include
#include

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

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

Q