循环队列-shenhailuanma-ChinaUnix博客

一个较巧妙的办法是将顺序队列臆造为一个环状的空间，如图3.13所示，称之为循环队列。从上述分析可见，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法估计所用队列的最大长度，则宜采用链队列。循环队列类型的模块说明如下：

//———循环队列—队列的顺序存储结构———
#define MAXQSIZE 100 //最大队列长度
typedef struct {
    QElemType *base； //初始化的动态分配存储空间
    int front； //头指针，若队列不空，指向队列头元素
    int rear； //尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue ；

图 3.13 循环队列

//循环队列的基本操作的算法描述
Status InitQueue (SqQueue &Q){ //构造一个空队列Q
    Q.base=( QElemType)malloc(MAXQSIZE*sizeof(QElemType))；
    if(!Q.base)exit(OVERFLOW)； //存储分配失败
    Q.front = Q.rear = 0；   return OK；}

Int QueueLength (SqQueue Q){ //返回Q的元素个数，即队列的长度
    return(Q.rear – Q.front + MAXQSIZE) % MAXQSIZE； }

Status EnQueue (SqQueue &Q， QElemType e){ //插入元素e为Q的新的队尾元素
    if((Q.rear+1)％MAXQSIZE==Q.front) return ERROR； //队列满
    Q.base[Q.rear] = e；  Q.rear = (Q.rear+1) ％ MAXQSIZE；     return OK； }

Status DeQueue (SqQueue &Q，QElemType &e){
//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
    if (Q.Front = = Q.rear) return ERROR；
    e = Q.base[ Q.front ]；   Q.front = (Q.front+1)％MAXQSIZE； return OK；}

原文：