> 队列是一种先进先出的线性表,它只允许在表的一段进行插入，而在另外一端删除元素。
> 
> 
> 
队列的顺序表示—用一维数组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 100
Typedef 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;
}
~~~
