循环队列

循环队列

为充分利用向量空间,克服”假溢出”现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在实际编程应用中来实现。

循环队列示意图

几个要点

  1. 图中有两个指针(其实就是两个整数型变量,因为在这里有指示作用,所以这里理解为指针)front、rear,一个指示队头,一个指示队尾。
  2. rear和front互相追赶着,这个追赶过程就是队列添加和删除的过程,如果rear追到head说明队列满了,如果front追到rear说明队列为空。
  3. 令队列空间中的一个单元闲置,使得队列非空时,Q.rear与Q.front之间至少间隔一个空闲单。
  4. 我们把它掰弯,用的是求余,这样两个值就不会跑出最大范围,并且可以实现弯曲的效果,所以说对于循环队列我们必须给定最大值Maxsize。这其实是我们臆想的,反正我们要做的就是利用循环来解决空间浪费的问题
  5. ( rear + 1 ) % maxsize == front 时,队列满
  6. rear == front 时,队列空

结构定义

1
2
3
4
5
6
7
8
#define Queue_size 5
typedef struct
{
int *base;
int front;
int rear;
int maxsize;
}SqQueue;

初始化

1
2
3
4
5
6
7
8
9
void InitQueue(SqQueue &q)
{
q.maxsize = Queue_size; //元素最大个数是maxsize-1
q.base = (int *)malloc(q.maxsize * sizeof(int));
if(!q.base)
exit(10);
q.front = q.rear = NULL;
return;
}

求队列元素个数

1
2
3
4
int QueueLength(SqQueue q)
{
return (q.rear - q.front + q.maxsize) % q.maxsize;
}

入队列

1
2
3
4
5
6
7
8
int EnQueue(SqQueue &q,int num)
{
if((q.rear + 1) % q.maxsize == q.front)
return -1; //队列满
q.base[q.rear] = num;
q.rear = (q.rear + 1) % q.maxsize;
return 0;
}

出队列

1
2
3
4
5
6
7
8
int DeQueue(SqQueue &q,int &e)
{
if(q.front == q.rear)
return -1; //队列空
e = q.base[q.front];
q.front = (q.front + 1) % q.maxsize;
return 0;
}

遍历队列

1
2
3
4
5
6
7
8
9
10
11
12
void TraverseQueue(SqQueue q)
{
int i=q.front;
printf("队中的元素是:\n");
while(i!=q.rear)
{
printf("%d ",q.base[i]);
// i++;
i = (i + 1) % q.maxsize;
}
printf("\n");
}