【 数据结构 】循环队列

ipqtjmqj 2020-03-23

队列是先进先出(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;

}

相关推荐