该队列是使用顺序存储方式进行存储。
顺序存储方式类比于数组，直接分配一整块连续的内存进行数据存储。
@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;
}
