小菜一步一步学数据结构之(六)队列-白红宇

队列是一种先进先出的线性表,它只允许在表的一段进行插入，而在另外一端删除元素。

队列的顺序表示—用一维数组base[M]

#define M 100//最大队列长度        Typedef struct{        QElemType *base;        int front;        int rear;        }SqQueue;

这里写图片描述

空队标志:front==rear入队:base[rear++]=x;出队:x=base[front++];

但是这样做存在一个问题，如下：

front=0 front≠0

rear=M时 rear=M时

再入队—真溢出再入队—假溢出

该怎样解决呢？

—-循环队列

base[0]接在base[M-1]之后          若rear+1==M          则令rear=0;          实现:利用“模”运算          入队:          base[rear]=x;          rear=(rear+1)%M;          出队:          x=base[front];          front=(front+1)%M;

又出现另外一个问题

解决方案:

1.另外设一个标志以区别队空、队满

2.少用一个元素空间:

队空:front==rear

队满:(rear+1)%M==front

循环队列

#define MAXQSIZE 100Typedef struct{ QElemType *base;//初始化的动态分配存储空间 int front;//头指针 int rear;//尾指针}SqQueue;

循环队列初始化

Status InitQueue(SqQueue &Q){ Q.base=new QElemType[MAXQSIZE]  if(!Q.base)exit(OVERFLOW);  Q.front=Q.rear=0;  return OK;}

循环队列的长度

int QueueLength(SqQueue Q){ return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}

循环队列入队

Status EnQueue(SqQueue &Q,QElemType e){ if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK;}

顺环队列出队

Status DeQueue(LinkQueue &Q,QElemType &e){   if(Q.front==Q.rear)   return ERROR;   e=Q.base[Q.front];   Q.front=(Q.front+1)%MAXQSIZE;   return OK;}