队列是插入位置和删除位置受限制的线性表,它只能在一端进行插入,而另一端进行删除元素,其只允许插入的一端称为队尾,只允许删除的一端称为队首。
由于队列中的元素在插入与删除时,两端的都要变化,所以需要两个指针,一个是front指向队首元素,另一个是rear指向队尾的下一个地址。有的课本上是front指针指向前一个地址,rear指向队尾元素,这都是为了算法的方便而设定的。
队列的两个特点:先进先出和有序性。
队列有两种存储表示:可用链表和顺序表来存储队列。
队列按存储结构分为两种:顺序队列(循环队列)和链式队列。
一、循环队列示意图
1.空循环队列示例:
2.入队循环队列示例:
3.队满循环队列示例:
二、循环队列代码
a.入队列代码
int InsertQueue(sqQueue &qu,int x) { if((qu.rear+1)%maxSize==qu.front) return 0; qu.rear=(qu.rear+1)%maxSieze qu.data[qu.rear]=x; return 1; }
b.出队列代码
int deleteQueue(sqQueue &qu,int &x) { if(qu.front==qu.rear) return 0; x=qu.data[qu.front];//先保存队头元素 qu.front=(qu.front+1)%maxSize; return 1; }
发表评论