《大话数据结构》读书笔记之 队列抽象数据类型（数组实现循环队列）
/*Name: 队列抽象数据类型（使用数组实现循环队列）
Copyright:
Author: 巧若拙
Date:15/09/14 09:08
Description:
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等
typedef struct{
ElemType data[MAXSIZE];//数组存储队列元素
int front;//队头指针
int rear; //队尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;
Status InitQueue(SqQueue *Q);//建立一个空的队列Q
Status QueueEmpty(SqQueue Q);//若队列为空，返回TRUE，否则返回FALSE
Status ClearQueue(SqQueue *Q);//将队列清空
int QueueLength(SqQueue Q);//返回队列Q的元素个数
Status DisplayQueue(SqQueue Q);//输出队列Q的所有元素
Status GetHead(SqQueue Q, ElemType *e);//用e返回队列Q的队头元素
Status LocateElem(SqQueue Q, ElemType e);//在队列Q中查找是否存在与给定值e相等的元素
Status EnQueue(SqQueue *Q, ElemType e);//在队列Q中插入新元素e
Status DeQueue(SqQueue *Q, ElemType *e);//删除队列Q的队头元素，并将该元素值赋给e
int main(void)
{
SqQueue a;
ElemType *p, e = 0;
int i;
InitQueue(&a);//建立一个空的队列
for (i=0; i<MAXSIZE; i++)
{
EnQueue(&a, i+1);//在队列Q中插入新元素e
}
DisplayQueue(a);
for (i=1; i<QueueLength(a); i+=2)
{
DeQueue(&a, &e);//删除队列Q的队列顶元素，并将该元素值赋给e
// printf("%d : e = %d\n", i, e);
}
printf("e = %d\n", e);
DisplayQueue(a);
e = 8;
if (LocateElem(a, e))//在队列Q中查找是否存在与给定值e相等的元素
{
printf("存在%d\n", e);
}
else
{
printf("不存在%d\n", e);
EnQueue(&a, e);//在队列Q中插入新元素e
}
DisplayQueue(a);
ClearQueue(&a);//将队列清空
DisplayQueue(a);
return 0;
}
/*
函数功能：建立一个空的队列Q
初始条件：无
操作结果：初始化队列Q。操作成功返回OK，否则返回ERROR
*/
Status InitQueue(SqQueue *Q)
{
Q->front = Q->rear = 0;
return OK;
}
/*
函数功能：判断队列是否为空
初始条件：顺序队列Q已经存在
操作结果：若队列为空，返回TRUE，否则返回FALSE
*/
Status QueueEmpty(SqQueue Q)
{
return (Q.front == Q.rear) ? TRUE : FALSE;
}
/*
函数功能：将队列清空
初始条件：顺序队列Q已经存在
操作结果：将队列清空。操作成功返回OK，否则返回ERROR
*/
Status ClearQueue(SqQueue *Q)
{
if (Q == NULL)
{
puts("队列不存在");
return ERROR;
}
Q->front = Q->rear = 0;
return OK;
}
/*
函数功能：返回队列Q的元素个数
初始条件：顺序队列Q已经存在
操作结果：返回队列Q的元素个数
*/
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
/*
函数功能：输出队列Q的所有元素
初始条件：顺序队列Q已经存在
操作结果：输出队列Q的所有元素。操作成功返回OK，否则返回ERROR
*/
Status DisplayQueue(SqQueue Q)
{
int i;
if (Q.front == Q.rear)
{
puts("空表");
return ERROR;
}
i = Q.front;
while (i != Q.rear)
{
printf("data[%d] = %d, ", i, Q.data[i]);
i++;
if (i >= MAXSIZE)
{
i -= MAXSIZE;
}
}
printf("\n");
return OK;
}
/*
函数功能：用e返回队列Q的队头元素
初始条件：顺序队列Q已经存在
操作结果：用e返回队列Q的队头元素。操作成功返回OK，否则返回ERROR
*/
Status GetHead(SqQueue Q, ElemType *e)
{
if (Q.front == Q.rear)
{
puts("空表");
return ERROR;
}
*e = Q.data[Q.front];
return OK;
}
/*
函数功能：在队列Q中查找是否存在与给定值e相等的元素
初始条件：顺序队列Q已经存在
操作结果：在队列Q中查找是否存在与给定值e相等的元素。找到返回TRUE，否则返回FALSE
*/
Status LocateElem(SqQueue Q, ElemType e)
{
int i = Q.front;
while (i != Q.rear)
{
if (Q.data[i] == e)
{
return TRUE;
}
i++;
if (i >= MAXSIZE)
{
i -= MAXSIZE;
}
}
return FALSE;
}
/*
函数功能：在队列Q中插入新元素e
初始条件：顺序队列Q已经存在
操作结果：在队尾插入新元素e。操作成功返回OK，否则返回ERROR
*/
Status EnQueue(SqQueue *Q, ElemType e)
{
if (Q->front == (Q->rear+1)%MAXSIZE) //队列满
{
puts("队列满");
return ERROR;
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE;
return OK;
}
/*
函数功能：删除队列Q的队头元素，并将该元素值赋给e
初始条件：顺序队列Q已经存在
操作结果：删除队列Q的队头元素，并将该元素值赋给e。
操作成功返回OK，否则返回ERROR
*/
Status DeQueue(SqQueue *Q, ElemType *e)
{
if (Q->front == Q->rear) //空表
{
puts("空表");
return ERROR;
}
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return OK;
}
