数据结构-队列之循环队列
将顺序队列臆造为一个环状的空间,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。
当队首指针q.front=MaxSize-1后,再前进一个位置就自动归0,可以通过除法取余运算(%)来实现。
初始时:q.front = q.rear=0
队首指针+1:q.front = (q.front + 1) % MaxSize;
队尾指针+1:q.rear = (q.rear + 1) % MaxSize;
队列长度:(q.rear+MaxSize-q.front)%MaxSize
循环队列的入队和出队示意图(摘抄):
那么,循环队列空和队满的条件是什么呢?显然,队空和队满时都存在q.front=q.rear,所以为了区分队空还是对满有三种处理方式:
1.牺牲一个单元来区分队空和队满,入队时少用一个队列单元,这是一种较为普遍的做法,约定“队头指针在队尾指针的下一位置作为队满的标志”,如图3-7(d2).
队满条件:(q.rear+1)%MaxSize == q.front.
队空条件仍为:q.front==q.rear.
队中元素个数:(q.rear-q.front+MaxSize)%MaxSize
2.类型中增设表示元素个数的数据成员,这样,则队空的条件为q.size==0;队满的条件为q.size==MaxSize,这两种情况都有q.front=q.rear
(个人感觉这种做法的弊端就是需要多引用一个成员,优点就是操作瞬间变得简单了很多有木有)
以下为代码的简单示例:
//队列之循环队列
#include "stdafx.h"
#define ElementType int
#define MaxSize 10
typedef struct {
ElementType data[MaxSize];
int front, rear;//队头指针和队尾指针
int size;//数据成员数量
}SeqQueue;
/*
初始化空队列
*/
void InitQueue(SeqQueue &q) {
q.front = q.rear = 0;
q.size = 0;
}
/*
判断队列是否为空
*/
bool QueueEmpty(SeqQueue q) {
if (q.size == 0) {
return true;
}
return false;
}
/*
入队操作
1.判断队列是否已满
2.队尾指针+1,因为是循环队列,所以通过除以MaxSize取模的方式处理,当队尾指针=MaxSize-1后,再前进一个位置自动归0
*/
bool EnQueue(SeqQueue &q,ElementType e) {
//判断队列是否已满
if (q.size == MaxSize) {
return false;
}
q.rear = (q.rear + 1) % MaxSize;
q.data[q.rear] = e;
q.size++;
return true;
}
/*
出队操作
1.判断队列是否为空
2.队首指针+1,因为是循环队列,所以通过除以MaxSize取模的方式处理,当队首指针=MaxSize-1后,再前进一个位置自动归0
*/
ElementType DeQueue(SeqQueue &q) {
//判断队列是否为空
if (q.size == 0) {
return NULL;
}
ElementType e = q.data[q.front];
q.front = (q.front + 1) % MaxSize;
q.size--;
return e;
}