数据结构选择排序,循环队列是顺序存储结构
文章目录顺序记忆结构循环排队代码实现注意
顺序存储结构
顺序存储结构是指用一组地址连续的存储单元依次存放从队头到队尾中的元素。
声明的两个指针rear和front分别用于指示队列端元素的下一个位置和队列头元素的位置。
初始化时rear=front=0
插入新元素时将末尾指针加1,元素退出队列时将开头指针加1。
但是,这样做有问题。 无论是进入队还是退出队,队首或队尾的指针都加1。 这样做有问题。就是元素出队所空出的空间无法被重新利用了
实际存储在队列中的元素数远远小于存储空间的大小,但不能入队操作。 这种现象称为假溢出。
循环队列循环队列通过将队列的顺序存储结构的一种实现方式顺序队列视为一个首尾相连的圆环来克服假溢出问题。
在循环队列中,头尾指针相同无法确定队列状态是空还是已满。 是因为这种情况下可能为空也可能为满。
减少循环队列中一个要素的空间,将“开头指针位于末尾指针的下一位置时”作为判断队列满的标志。
代码实现#define MAXQSIZE 100 //队列的最大长度typedef struct{ int *base; int front动态分配存储空间; //开头指针,如果队列不为空则指向开头要素int rear; //末尾指针,int queueSize,指向末尾元素的下一个位置; } sq队列; boolinitqueue(sqqueueq,int maxSize ) { Q.base=new int[maxSize]; if (! Q.base () exit )-1; } Q.queueSize=maxSize; Q.front=Q.rear=0; 返回真; }boolenqueue(sqqueueq,int e ) if ) ) q.rear1) % Q.queueSize==Q.front ) { return false; } Q.base[Q.rear]=e; q.rear=(q.rear1) % Q.queueSize; 返回真; }booldequeue(sqqueueq,int e ) if ) q.front==q.rear ) { return false; } e=Q.base[Q.front]; q.front=(q.front1) % Q.queueSize; 返回真; 注意如果rear=front,则可以确定队列为空。 如果% size==front,则可以确定队列已满。 % size是队列的长度