解决顺序表实现队列的假溢出的循环队列

循环队列的参考视频:https://www.bilibili.com/video/BV1nJ411V7bd?p=60

问题:什么是顺序队列的假溢出?

从队首倒到队尾完全占用了分配的空间,是溢出。相反,队尾元素占用了分配的最后一个空间,队首元素还是占有的不是第一个分配的空间,相当于队列对外是满的,但是内部空间利用不充分,还有剩余,此时就称为假溢出。

解决假上溢的方法-引入循环队列

把把队列首元素queue[front=0] 接在queue[MAXQSIZE-1]之后,若rear+1 == MAXQSIZE,则令rear=0;
解决办法:使用模运算(%)

//插入元素:
queue[rear] = x;
rear = ( rear + 1 ) % MAXQSIZE;

//删除元素:
x = queue[front];
front = ( front + 1) % MAXQSIZE;

相当于下表为0的元素的前驱变成了原队尾(MAXQSIZE-1)的后继。

遇到新问题

判断队列空或满时,都是 front == rear

解决方案:

  1. 设置标志,以区别队空、队满
  2. 另设一个变量,计算元素个数
  3. 少利用一个空间(以下编码使用这种方式)

少用一个空间如何区别队满?

队满判断条件:front ==(rear+1)% MAXQSIZE;

实现代码

/*
 * @Author: jinbo.ma
 * @Mail: 18710648068@163.com
 * @Date: 2021-05-04 09:39:21
 * @LastEditTime: 2021-05-05 16:02:41
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXQSIZE 6

int queue_length (int front, int rear) {
    return (rear - front + MAXQSIZE) % MAXQSIZE;
}

int entry_queue (int *q, int *front, int *rear, int data) {
    printf ("data=%d\n", data);
    //判断队满
    if ( (*rear+1)%MAXQSIZE == *front ) {
        return 0;
    }

    q[*rear] = data;
    *rear = (*rear + 1) % MAXQSIZE;

    return 1;
}

int exit_queue (int * q, int *front, int *rear, int *data) {
    //判断队空
    if (*front == *rear) {
        return 0;
    }
    
    *data = q[*front];
    *front = (*front + 1) % MAXQSIZE;
    
    return 1;
}

/**
 * 顺序表-循环队列之实现
 */
int main() {

    int queue[MAXQSIZE] = {0}, front = 0, rear = 0;
    int data;
    
    //空队出队操作
    if ( exit_queue(queue, &front, &rear, &data) )  {
        printf("空队列出队成功这是不可能的事情!data=%d\n\n", data);
    } else {
        printf("空队列出队失败才是正常的, front=%d, rear=%d\n\n", front, rear);
    }
    
    printf("\n----------------------------------------------------------------\n");
    //求空队列的长度
    printf("queue length=%d\n", queue_length(front, rear) );

    printf("\n----------------------------------------------------------------\n");
    //试验真溢出
    for (int i = 0; i <= MAXQSIZE; i++) {
        printf("i=%d\n", i);
        if ( entry_queue(queue, &front, &rear, 10+i) ) {
            printf("data=%d 入队成功: front=%d, rear=%d\n", 10+i, front, rear);
        } else {
            printf("data=%d 入队失败: front=%d, rear=%d\n", 10+i, front, rear);
        }
    }

    //求队列长度,牺牲一个空间满足了判断队满的情况,故而此时队列长度为MAXQSIZE-1
    printf("queue length=%d\n", queue_length(front, rear) );
    printf("\n----------------------------------------------------------------\n");
    //出队四个元素
    for (int i = 0; i < MAXQSIZE-2; i++) {
        printf("i=%d\n", i);
        if ( exit_queue(queue, &front, &rear, &data) ) {
            printf("data=%d 出队成功: front=%d, rear=%d\n", data, front, rear);
        } else {
            printf("data=%d 出队失败: front=%d, rear=%d\n", data, front, rear);
        }
    }

    printf("\n----------------------------------------------------------------\n");
    //假如不是循环队列,此时是不能入队的,继续入队测试循环队列
    for (int i = 0; i <= MAXQSIZE; i++) {
        printf("i=%d\n", i);
        if ( entry_queue(queue, &front, &rear, 15+i) ) {
            printf("data=%d 入队成功: front=%d, rear=%d\n", 15+i, front, rear);
        } else {
            printf("data=%d 入队失败: front=%d, rear=%d\n", 15+i, front, rear);
        }
    }
    //此时队列长度又是MAXQSIZE-1
    printf("queue length=%d\n", queue_length(front, rear) );

    return 0;
}

执行结果:

空队列出队失败才是正常的, front=0, rear=0

----------------------------------------------------------------
queue length=0

----------------------------------------------------------------
i=0
data=10
data=10 入队成功: front=0, rear=1
i=1
data=11
data=11 入队成功: front=0, rear=2
i=2
data=12
data=12 入队成功: front=0, rear=3
i=3
data=13
data=13 入队成功: front=0, rear=4
i=4
data=14
data=14 入队成功: front=0, rear=5
i=5
data=15
data=15 入队失败: front=0, rear=5
i=6
data=16
data=16 入队失败: front=0, rear=5
queue length=5

----------------------------------------------------------------
i=0
data=10 出队成功: front=1, rear=5
i=1
data=11 出队成功: front=2, rear=5
i=2
data=12 出队成功: front=3, rear=5
i=3
data=13 出队成功: front=4, rear=5

----------------------------------------------------------------
i=0
data=15
data=15 入队成功: front=4, rear=0
i=1
data=16
data=16 入队成功: front=4, rear=1
i=2
data=17
data=17 入队成功: front=4, rear=2
i=3
data=18
data=18 入队成功: front=4, rear=3
i=4
data=19
data=19 入队失败: front=4, rear=3
i=5
data=20
data=20 入队失败: front=4, rear=3
i=6
data=21
data=21 入队失败: front=4, rear=3
queue length=5

上一篇:队列


下一篇:3-2-queue_队列_链式存储