【 数据结构 】循环队列
队列是先进先出(first in first out)的线性表,简称 FIFO。
假设循环队列:
队头:front
队尾:rear
最大尺寸:queue size
队列满:(rear + 1)% queue size == front
通用队列长度计算: (rear - front + queue size)% queue size
存储结构代码示例
typedef int QElemType; /* 队列内数据的类型 */
/* 循环队列的顺序存储结构 */
typedef struct
{
QElemType date[MAXSIZE];
int front; /* 头指针 */
int rear; /* 尾指针,若队列不为空,指向下一个入队位置 */
}SqQueue;
/* 初始化一个空队列 */
int InitQueue(SqQueue *Q)
{
Q->front = 0;
Q->rear = 0;
return OK;
}
/* 循环队列求长度 */
int QueueLenght(SqQueue *Q)
{
return (Q.rear - Q.front + MAXSIZE)% MAXSIZE;
}
/* 循环队列的入队操作 */
int EnQueue(SqQueue *Q, QElemType e)
{
if((Q->rear + 1)%MAXSIZE == Q->front) /* 判断队列满 */
return ERROR;
Q->data[Q->rear] = e; /* 新元素给队尾 */
Q->rear = (Q->rear + 1)%MAXSIZE; /* rear指针后移一位 */
/* 若到最后则转到数组头 */
return OK;
}
/* 循环队列的出队操作 */
int EnQueue(SqQueue *Q, QElemType *e)
{
if(Q->rear == Q->front) /* 判断队列空 */
return ERROR;
*e = Q->data[Q->front] ; /* 队头元素给e */
Q->front= (Q->front+ 1)%MAXSIZE; /* front指针后移一位 */
/* 若到最后则转到数组头 */
return OK;
}