小甲鱼数据结构30讲循环队列入队操作的红色代码实现的结果并不能完全填满数组空间....

圣狄雅哥

InsertQueue(cycleQueue *q, ElemType e)
{
if( (q->rear+1)%MAXSIZE == q->front )
return; // 队列已满
q->base[q->rear] = e;
q->rear = (q->rear+1) % MAXSIZE;
}

圣狄雅哥

//初始化循环队列   
initQueue(cycleQueue *q)
    {
    q->base = (ElemType *) malloc (MAXSIZE * sizeof(ElemType));
    if( !q->base )
    exit(0);
    q->front = q->rear = 0;
    }


q->rear相当于数组下标，而q->base[q->rear]赋值之前为空的，所以当q->rear+1==q->front时，前面的判断语句:if ( (q->rear+1) % MAXSIZE == q->front )   return; 这段语句就已经跳出了入队操作，实际上q->rear还并未赋值。

人造人

要学会调试呀
教你一招，把变量具体化，也就是说在某时某刻某个变量中存储了什么
下面演示一下

当initQueue函数执行完后，q->front 和 q->rear 都等于 0，q->base 已经申请到存储空间
第一次执行InsertQueue函数时
会执行这个 if( (q->rear+1)%MAXSIZE == q->front )
那么if 的条件是真还是假呢，计算一下

(q->rear+1)%MAXSIZE == q->front
因为是第一次执行InsertQueue函数，所以 q->rear 等于 0， q->front 也等于 0
也就是 (0 + 1) % MAXSIZE == 0
这样还是无法计算，那么再来另一招，化繁为简，如果一个值在某个时刻可以存在许多值，那么选择一个最简单，最适合计算的
在这里我把 MAXSIZE 定为 10，因为 10 第一是数字小，第二是计算边界方便，因为 MAXSIZE 是 10，所以 q->base[q->rear]
  q->rear 的范围就是 0 - 9，如果 MAXSIZE 是 10000，这样数字太大，计算起来不方便，q->rear 的值也太多，如果 MAXSIZE 是 31，数字是不大，不过后面有一个 1，计算起来还是不方便，总的来说就是选一个方便计算的值
在这里我把 MAXSIZE 定为 10
也就是说
#define MAXSIZE 10
这里我就这样了

(0 + 1) % MAXSIZE == 0
            ||
(0 + 1) % 10 == 0
            ||
1 == 0
结果为False
也就是队列未满， return; // 队列已满      不会执行

q->base[q->rear] = e;
            ||
q->base[0] = e;


q->rear = (q->rear+1) % MAXSIZE;
                  ||
q->rear = (0 + 1)  % 10;
                  ||
q->rear = 1;

下一次，return; // 队列已满      还是不会执行

q->base[q->rear] = e;
            ||
q->base[1] = e;

q->rear = (q->rear+1) % MAXSIZE;
                ||
q->rear = (1 + 1) % 10;
                ||
q->rear = 2;

q->rear 就这样0 1 2 3 4 5 6 7 8 一直到 8（应该是到 9），因为 9 是那个特别需要关注的 它（应该是这个 '它'吧^_^）的前一个也需要特别关注一下

当 q->rear 等于 8 时
(q->rear+1)%MAXSIZE == q->front
                ||
(8 + 1) % 10 == 0 // 这里假设一直入列，不出列
9 == 0
结果为False
也就是队列未满， return; // 队列已满      不会执行

q->base[q->rear] = e;
        ||
q->base[8] = e;

q->rear = (q->rear+1) % MAXSIZE;
        ||
q->rear = (8 + 1) % 10;
        ||
q->rear = 9;


现在终于到了关键的地方了
q->rear 等于 9

(q->rear+1)%MAXSIZE == q->front
        ||
(9 + 1) % 10 == 0
        ||
0 == 0
队列已满



如果是既入列又出列
例如 3次入列1次出列，之后一直入列
那么
q->rear 等于 9 时

(q->rear+1)%MAXSIZE == q->front
        ||
(9 + 1) % 10 == 1 因为有1次出列，所以 q->front 等于 1
        ||
0 == 1
队列未满，因为 q->base[0] 已出列，现在 q->base[0] 是空着的

q->base[q->rear] = e;
        ||
q->base[9] = e;

q->rear = (q->rear+1) % MAXSIZE;
        ||
q->rear = (9 + 1) % 10;
        ||
q->rear = 0;



的确是在队列满的时候还有1个存储空间，但是把还有1个存储空间认为是队列满，代码就可以很简单，就像现在这样
如果队列满时没有存储空间，你认为代码该如何改？
把   (q->rear + 1) % MAXSIZE == q->front
改为 q->rear % MAXSIZE == q->front
？？？
但是这样还是不行

不是做不到 在队列满的时候没有存储空间，在队列满的时候没有存储空间 必然会增加代码量和代码复杂度，在 代码量、代码复杂度 和 这1个存储空间中，你选哪一个？这就是一个选择，仅此而已，就像 if(条件) 条件符合执行;  ^_^

圣狄雅哥

人造人 发表于 2018-2-2 14:15
要学会调试呀
教你一招，把变量具体化，也就是说在某时某刻某个变量中存储了什么
下面演示一下

大哥你真是太用心了，解答详细而深刻，我看完很感动和启发。确实我想了那段代码不好改，对于整个程序的复杂度和理解难度上来说就算空一个位置才满栈也是赔得起的。当时我看这部分以为是我理解错了，看来是我理解的不够全面。

人造人

圣狄雅哥 发表于 2018-2-2 20:26
大哥你真是太用心了，解答详细而深刻，我看完很感动和启发。确实我想了那段代码不好改，对于整个程序的复 ...

^_^