循环队列

一晚上到处转弯,本来顺序队列说好的出队之后,所有元素都要相应移动的,这会又突然出来一个循环队列,看样子不是这规矩

队列如果后面满了,就再从头开始,也就是头尾相接的循环,这种头尾相接的顺序存储结构为循环队列

由于空队列的时候,front等于rear,可如今这样队列后面满了就从头开始的,那么整个队列满了的时候front也等于rear,就会产生矛盾,弄一个flag不太方便,所以设定队列为空的条件还是front = rear,但是队列满了的时候,需要空出一个元素,也就是根本不存在整个队列都塞满的情况

由于rear可能比front大,也可能比front小,所以尽管它们只相差一个位置的时候就是满的情况,但是也有可能是相差了整整一圈,所以假如队列最大尺寸是QueueSize,那么队列满了的条件是:

(rear + 1) % QueueSize == front

当rear > front的时候,队列长度为:rear-front

当rear < front的时候,队列长度为:(QueueSize – front)+(0 + rear)=(rear – front + QueueSize)% QueueSize

因此,队列的长度为:(rear – front + QueueSize) % QueueSize

写了半天,纠结于如何遍历输出,而push和pop还是很简单的,其实用while + %还是比较容易得到循环遍历的规则:

#include <stdio.h>
#include <malloc.h>

#define MAXSIZE 5

typedef struct {
    int data[MAXSIZE];
    int front;
    int rear;
}SqQueue;

int InitQueue(SqQueue *s){
    s->front = 0;
    s->rear = 0;
    return 0;
}

int PushQueue(SqQueue *s, int num){
    if ((s->rear + 1) % MAXSIZE == s->front)
        return 0;
    s->data[s->rear] = num;
//  ++s->rear;
    s->rear = (s->rear + 1) % MAXSIZE;
    return 0;
}

int PopQueue(SqQueue *s){
    if (s->rear == s->front)
        return 0;
    s->front = (s->front + 1) % MAXSIZE;
    return 0;
}

int main(){
    SqQueue *q;
    q = (SqQueue *)malloc(sizeof(SqQueue));
   
    InitQueue(q);

    PushQueue(q, 1);
    PushQueue(q, 2);
    PushQueue(q, 3);
    PushQueue(q, 4);
//    PushQueue(q, 5);

    PopQueue(q);
    PopQueue(q);

    PushQueue(q, 5);
    PushQueue(q, 6);

    while (q->front != q->rear){
        printf(“data[%d]: %d\n”, q->front, q->data[q->front]);
        q->front = (q->front + 1) % MAXSIZE;
    }

    return 0;
}

发表回复