> 隊列是一種先進先出的線性表,它只允許在表的一段進行插入，而在另外一端刪除元素。?
> ?
> ?
> 
隊列的順序表示—用一維數組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;
}
~~~
