• 循环顺序队列的描述与表示
• 循环顺序队列的操作定义接口
• 循环顺序队列的操作实现

循环顺序队列的描述与表示

队列

队列(Queue)是一种只允许在序列两端进行操作的线性结构。和日常生活中排队等待买票的法则相似，排在队头的人先买到票并离开队列，而新来的人则加入队尾等候。因此很容易理解队列仅允许在队头出队，在队尾入队。

循环顺序队列

采用顺序存储结构的队列成为顺序队列，和顺序栈相同，我们也采用动态分配空间的方式来获取这个存储空间。那么何为循环队列呢？为什么我们需要循环队列呢？试想，我们在排队等候买票的时候是不是有这样的场景，前面的人买完票就离开队列，而这时后面的人是不是每个人都要往前挪动一个位置呢？那么如果我们以同样的方法来处理我们的队列，每当一个元素出队的时候，就必须把后面所有的元素往前挪动一个位置，这样必然导致算法效率变低。因此，我们想到了将队列的首位相连，构成了一个循环队列。

循环队列类型定义如下：

typedef struct {
  ElemType* base;   //循环队列存储空间的基址
  int front;        //队头位标（指向队头元素的位置）
  int rear;         //队尾位标（指向队尾元素的下一个位置）
  int maxSize;      //队列的最大长度
} SqQueue;

我们采用循环队列解决了元素出队时需要移动全部元素的问题，但是出现了一个新问题，在我们判空的时候我们采用的是判断队头位标和队尾位标是否一致的方式，而放在循环队列里，因为队列已经首尾相接，于是我们会发现这时候如果队列满了，队头位标和队尾位标也是一致的，解决方式有很多，比如：

1. 设置标志域标识队列的空或满，使用标志域数组同步记录
2. 设置长度域记录队列中元素个数，判断长度域即可
3. 少用一个元素空间，采用循环加一的方式，如果发现Q.front == (Q.rear + 1) % Q.maxSize则认为队满。

以下的实现中我们采用了第三种方式。

本文中预定义的说明

预定义常量和类型

//函数结果状态代码
#define TRUE      1
#define FALSE     0
#define OK        1
#define ERROR     0
#define OVERFLOW -1

typedef int Status; // 用作函数值类型，表示函数结果状态

数据结构（存储结构）的表示

数据结构的表示用类型定义(typedef)描述。数据元素类型约定为ElemType，读者在使用该数据类型时自行定义，如int、char等简单类型。

扩展引用调用

为了便于算法描述，我们使用了 C++ 语言中的引用调用参数传递方式。

循环队列操作定义接口

我们定义了关于循环队列操作的如下接口：

// 构造一个空队列 Q，最大队列长度为 size
Status InitQueue_Sq(SqQueue &Q, int size);
// 销毁队列 Q，Q不再存在
void DestoryQueue_Sq(SqQueue &Q);
// 将队列置空
void ClearQueue_Sq(SqQueue &Q);
// 判断队列是否为空，是返回 TRUE，否则返回 FALSE;
Status QueueEmpty_Sq(Squeue Q);
// 返回队列 Q 中元素个数，即队列长度
int QueueLength_Sq(SqQueue Q);
// 取队头元素，用 e 返回，并返回 OK，若队列为空，返回 ERROR
Status GetHead_Sq(SqQueue Q, ElemType &e);
// 元素 e 入队，即在队尾插入元素 e
Status EnQueue_Sq(SqQueue &Q, ElemType &e);
// 队头元素出队，并用 e 返回
Status DeQueu_Sq(SqQueue &Q, ElemType &e);

初始化循环队列

• 分配存储空间
• 置队列为空

Status InitQueue_Sq(SqQueue &Q, int size)
{
  Q.base = (ElemType*)malloc(size * sizeof(ElemType));
  if (NULL == Q.base)
    return OVERFLOW;
  Q.maxSize = size;
  Q.front = 0;
  Q.rear = 0;

  return OK;
}

销毁队列

void DestoryQueue_Sq(SqQueue &Q)
{
  free(Q.base);
}

将队列置空

void ClearQueue_Sq(SqQueue &Q)
{
  Q.front = 0;
  Q.rear = 0;  
}

判断队列是否为空

Status QueueEmpty_Sq(SqQueue Q)
{
  if (Q.front == Q.rear)
    return ERROR;
}

返回队列长度

int QueueLength_Sq(Squeue Q)
{
  return (Q.rear - Q.front + Q.maxSize) % Q.maxSize;
}

取队头元素

Status GetHead_Sq(SqQueue Q, ElemType &e)
{
  if (QueueEmpty_Sq(Q))
    return ERROR;
  e = Q.base[Q.front];

  return OK;
}

入队

Status EnQueue_Sq(SqQueue &Q, ElemType e)
{
  if ((Q.rear + 1) % Q.maxSize == Q.front)
    return ERROR;
  Q.base[Q.rear] = e;
  Q.rear = (Q.rear + 1) % Q.maxSize;

  return  OK;
}

出队

Status DeQueue_Sq(SqQueue &Q, ElemType &e)
{
  if (Q.front == Q.rear)
    return ERROR;
  e = Q.base[Q.front];
  Q.front = (Q.front + 1) % Q.maxSize;

  return OK;
}

参考资料

《数据结构》（吴伟民，李小妹）