循环队列.cpp

该队列是使用顺序存储方式进行存储。
顺序存储方式类比于数组，直接分配一整块连续的内存进行数据存储。

@author:Kadima

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;     //用作函数值类型，表示函数结果状态
typedef int ElemType;

//循环队列:循环队列为空的条件是Q.front==Q.rear,循环队列为满的条件是Q.front==(Q.rear+1)%Q.maxSize,即少用一个元素
typedef struct {
    ElemType * elem;    //存储空间的基址
    int front;          //队头位标
    int rear;           //队尾位标，指示队尾元素的下一位置
    int maxSize;        //最大长度
} SqQueue;

/*1.初始化操作：构造一个空队列Q，最大队列长度为size*/
Status InitQueue_Sq(SqQueue &Q, int size){//构造一个空队列
    Q.elem = (ElemType *)malloc(size*sizeof(ElemType));//分配存储空间
    if(NULL==Q.elem)    return OVERFLOW;
    Q.maxSize = size;
    Q.front = Q.rear = 0;//置Q位空队列
    return OK;
}


/*2.出队操作：若队列不空则删除当前队列Q中的头元素，用e返回其值，并返回OK；否则ERROR*/
Status DeQueue_Sq(SqQueue &Q, ElemType &e){
    if(Q.front == Q.rear)   return ERROR;   //队空报错
    e = Q.elem[Q.front];
    Q.front = (Q.front + 1) % Q.maxSize;//Q.front循环加1
    return OK;
}


/*3.入队操作：在当前队列的尾元素之后插入元素e为新的尾元素*/
Status EnQueue_Sq(SqQueue &Q, ElemType e){
    //若当前队列不满，在队列的尾元素之后，插入元素e为新的队列尾元素
    if((Q.rear + 1)%Q.maxSize==Q.front) return ERROR;
    Q.elem[Q.rear] = e;
    Q.rear = (Q.rear + 1) % Q.maxSize;
    return OK;
}


/*销毁队列Q，Q不再存在*/
Status DestroyQueue_Sq(SqQueue &Q){
    Q.front = Q.rear = 0; //置队为空
    Q.maxSize = 0;
    free(Q.elem);   //释放指针指向的内存
    Q.elem = NULL; //把基址设为null,悬空。防止指针在后面不小心又被解引用了。
    return OK;
}

/*将Q置为空队列*/
void ClearQueue_Sq(SqQueue &Q){
    Q.front = Q.rear = 0;
}

/*若队列Q为空队列则返回TRUE，否则FALSE*/
Status QueueEmpty_Sq(SqQueue Q){
    if(Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}

/*返回队列Q中的元素个数，即队列的长度*/
int QueueLength_Sq(SqQueue Q){
    if(Q.rear >= Q.front)
        return (Q.rear - Q.front);
    else
        return (Q.rear - Q.front + Q.maxSize);      //Q.maxSize - (Q.front - Q.rear)
}

/*若队列不空，则用e返回Q的队列头元素，并返回OK；否则ERROR*/
Status GetHead_Sq(SqQueue Q, ElemType &e){
    if(Q.front == Q.rear)
        return ERROR;
    else{
        e = Q.elem[Q.front];
        return OK;
    }
}



/*
车厢编号
假设队列元素是char类型，'H'表示硬座，'S'表示软卧，队列A表示一组硬座和卧铺混编的车厢。
要求把队列A中的硬座车厢移动到队列B，队列A中的卧铺车厢移动到队列C，同时保留原有硬座车厢之间和软卧车厢之间的先后顺序不变。
*/
void Arrange(SqQueue A, SqQueue &B, SqQueue &C){
    ElemType e; //书上是char类型，但是我把ElemType用define定义为int型，故报错
    InitQueue_Sq(B, A.maxSize); //空的硬座队列B
    InitQueue_Sq(C, A.maxSize); //空的硬座队列C
    while(FALSE == QueueEmpty_Sq(A)){//依次处理队列A中的每个车厢
        DeQueue_Sq(A, e);
        if(e == 'H')    EnQueue_Sq(B, e);//加入硬座队列B
        else    EnQueue_Sq(C, e);//加入软卧队列C
    }
}


int main(){
    SqQueue A, B, C;
    char c[30];
    int i = 0;
    int n = 0;
    ElemType e;

    printf("输入括号串:");
    scanf("%s",c);
    n = strlen(c);
    InitQueue_Sq(A, n+1);   //注意：此处记得要将字符串长度加1，因为队列是少用一个元素空间来进行判空的
    for(i=0;i<n;i++){
        EnQueue_Sq(A, c[i]);
    }
    Arrange(A, B, C);

    printf("B队列长度为:%d\n",QueueLength_Sq(B));
    printf("B队列:");
    while(FALSE == QueueEmpty_Sq(B)){//依次处理队列A中的每个车厢
        DeQueue_Sq(B, e);
        printf("%c",e);
    }
    printf("\n");

    printf("C队列长度为:%d\n",QueueLength_Sq(C));
    printf("C队列:");
    while(FALSE == QueueEmpty_Sq(C)){//依次处理队列A中的每个车厢
        DeQueue_Sq(C, e);
        printf("%c",e);
    }
    printf("\n");
    return 0;
}