顺序队列出队列的特点

上篇草草了事以为OK,实际上根本没弄清楚FIFO的特点,那段程序输出的结果是从下标3开始的,也就是0,1,2三个元素给pop了之后,原封不动地将其他元素输出来,本以为自己做完了,其实一开始就错了

队列的入队只需要队尾插入一个元素,然后下标加1;但是队列的出队是在队头,也就是下标为0的位置,如果有元素出队,其它所有的元素都必须要向前移动,以保证队列的队头,也就是下标为0的位置不能为空

队列出队列一定要全部移动,原因是假如不移动,有元素出队,队头就会后移,下标就会增加,比如上篇错误的程序,队列先有10个元素,然后出队列了3个元素,剩下输出了data[3]~data[9],而且下标就是3~9,队头是data[3],而队列总个数为10,也就是没满,还可以插3个元素,但是假如此时入队,队尾已经没有位置了,因为队尾已经在data[9],再移动就相当于溢出了,而实际上队列并没有满,这就造成了错误

所以pop的部分应该修改为:

出队一个元素,所有元素前移一位,然后队尾减1,即:

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

#define MAXSIZE 10

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

int QueuePush(SqQueue *S, int num){
    S->data[S->rear] = num;
    ++S->rear;
    return 0;
}

int QueuePop(SqQueue *S){
//    ++S->front;
    int i;
    for (i = 0; i < S->rear; i++){
        S->data[i] = S->data[i + 1];
    }
    –S->rear;
    return 0;
}

int main(){
    SqQueue *s;
    s = (SqQueue *)malloc(sizeof(SqQueue));
    s->front = 0;
    s->rear = 0;

    /*
    int i;
    for (i = 0; i < MAXSIZE; i++){
        s->data[i] = i;
        ++s->rear;
    }*/

    int i;
    for (i = 0; i < MAXSIZE; i++){
        QueuePush(s, i);
    }

    QueuePop(s);
    QueuePop(s);
    QueuePop(s);

    int j = 0;
    for (j = s->front; j < s->rear; j++){
        printf(“data[%d] = %d\n”, j, s->data[j]);
    }
    free(s);
    return 0;
}

发表评论