MENU

C语言 循环队列及基本操作实现

2018 年 03 月 07 日 • 日常作业

《数据结构》实验让写一个栈,我写了顺序栈。这里是我的代码,供将来自己检索,和大家参考之用。

/* 
    队列的结构和基本操作
    By Xu Wei on 08/12/17 under GCC 5.4.0
*/
#include <malloc.h>
#include <stdio.h>

#define ERROR -1
#define OK 1
#define TRUE 1
#define FALSE 0

/*
    除了在外面 define DataType 和 MAXNUM 外,还应该
    define SafeMode,值有 TRUE 和 FALSE
    define SafeData,值的类型为 DataType,作为出队时安全数据填充
*/

typedef struct Queue{
    int front;
    int rear;
    DataType data[MAXNUM];
} Queue;

/*
    初始化队列
    @返回 队列的指针,失败返回 NULL
    @使用示例
    Queue *queue = initQueue();
    if(!queue) printf("队列建立失败,可能内存不足!");
*/
Queue *initQueue(){
    if(MAXNUM <= 0) return NULL;
    if(SafeMode != TRUE && SafeMode != FALSE) return NULL;

    Queue *Q = (Queue *)malloc(sizeof(Queue));
    if(!Q) return NULL;
    Q->front = Q->rear = -1;
    return Q;
}

/*
    判断队空
    @参数 Q 队列的指针
    @返回 为空返回 TRUE,非空返回 FALSE,失败返回 ERROR
*/
int isQueueEmpty(Queue *Q){
    if(!Q) return ERROR;

    return Q->front == -1 && Q->rear == -1 ? TRUE : FALSE;
}

/*
    判断队满
    @参数 Q 队列的指针
    @返回 为满返回 TRUE,不满返回 FALSE,失败返回 ERROR
*/
int isQueueFull(Queue *Q){
    if(!Q) return ERROR;

    return (Q->rear - Q->front == MAXNUM) || (Q->front == Q->rear && Q->front != -1) ? TRUE : FALSE;
    // front == rear && !isQueueEmpty()
}

/*
    元素入队
    @参数 Q 队列的指针
          data 要入队的元素
    @返回 已入队元素的索引号,失败返回 ERROR
*/
int inQueue(Queue *Q, DataType data){
    if(!Q) return ERROR;
    if(isQueueFull(Q) == TRUE) return ERROR;

    Q->rear = (Q->rear + 1) % MAXNUM;
    Q->data[Q->rear] = data;
    return Q->rear;
}

/*
    元素出队
    @参数 Q 队列的指针
          pd 要出队到的元素的空间,若不需存放可设为 NULL
    @返回 已出队元素的原索引号,失败返回 ERROR
*/
int outQueueTo(Queue *Q, DataType *pd){
    if(!Q) return ERROR;
    if(isQueueEmpty(Q) == TRUE) return ERROR;

    int frontNum = Q->front + 1;
    if(pd) *pd = Q->data[frontNum];
    if(SafeMode == TRUE) Q->data[frontNum] = SafeData;
    if(frontNum == Q->rear) 
        Q->front = Q->rear = -1; //队空时更改指示以便不会与判满混淆
    else
        Q->front = (frontNum + 1) % MAXNUM - 1;
    return frontNum;
}

/*
    元素出队,而不存放出队元素的值
    @参数 Q 队列的指针
    @返回 已出队元素的原索引号,失败返回 ERROR
*/
int outQueue(Queue *Q){
    return outQueueTo(Q, NULL);
}

/*
    读队头,而不进行异常校验(危险)
    @参数 Q 队列的指针
    @返回 队头元素
*/
DataType readQueue(Queue *Q){
    return Q->data[Q->front + 1];
}

/*
    输出队
    @参数 Q 队列的指针
          printNode 输出函数的指针,该函数有两个参数,参数1接收队列中的元素,参数2接收对应索引号
          sep 分隔符字符串
    @返回 成功返回 OK,失败返回 ERROR
    @使用示例
    void myPrint(int data, int index){
        printf("[%d]%d", index, data);
    }
        printQueue(queue, myPrint, ", ");
*/
int printQueue(Queue *Q, void (*printNode)(DataType,int), char *sep){
    if(!Q) return ERROR;

    if(isQueueEmpty(Q)) return OK; //队列为空无需输出
    int rearNext = (Q->rear + 1) % MAXNUM;
    int i = Q->front + 1, flag = 0;
    do{
        if(flag) printf("%s", sep);
        printNode(Q->data[i], i);
        flag = 1;
        i = (i + 1) % MAXNUM;
    }while(i!=rearNext); //不可将此条件作为 while do 循环条件,因为第一次循环时可以让其成立(队满)
    return OK;
}