《大话数据结构》读书笔记之 队列抽象数据类型（数组实现循环队列）

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