c - 将队列数据结构作为数组实现的问题

Question

这段代码将简单的队列数据结构作为数组实现

#include <stdio.h>
#define Q_MAX_SIZE 255
#include <stdbool.h>
struct queue
{
    int* pointer;
    int* currentValue;
    int max, count, theQueue[Q_MAX_SIZE];
};

void initQueue(struct queue*);
bool pushQueue(struct queue*, int);
int* popQueue(struct queue*);

int main(void)
{
    int i, j, num = 0;
    struct queue obj[5];

    for(i=0; i<5; i++)
    {
        initQueue(&obj[i]);

        for(j = 0; j<3; j++)
        {
            num++;
            pushQueue(&obj[i], num);
        }
        num = 0;
    }

    for(i=0; i<5; i++)
    {
        printf("Queue[%d]:\n", i);
        int* inputobj;
        inputobj = popQueue(&obj[i]);

        while(inputobj != NULL)
        {
            printf("Queue[No.%d] = %d\n", i, *inputobj);
            inputobj = popQueue(&obj[i]);
        }
        putchar('\n');
    }

    puts("done..!");

    return 0;
}

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

void initQueue(struct queue *Q)
{
    Q->pointer = Q->theQueue;
    Q->max = Q_MAX_SIZE;
    Q->count = 0;
}

bool pushQueue(struct queue *Q, int input)
{
    if(Q->count < Q->max)
    {
        *Q->pointer = input;
        Q->pointer++;
        Q->count++;
        return 1;
    }
    else
        return 0;
}

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

int* popQueue(struct queue *Q)
{
    int i;
    if(Q->count > 0)
    {
        Q->currentValue = Q->theQueue;
        Q->pointer--;
        Q->count--;

        for(i=0; i < Q->count; i++)
        {
            int* currentPtr = Q->theQueue + i;
            int* nextPtr = currentPtr + 1;
            *currentPtr = *nextPtr;
        }
        return Q->currentValue;
    }

    else
        NULL;
}

此行函数 popQueue() 中的代码有问题:

Q->currentValue = Q->theQueue;

这是输出不正确的工作

output:
Queue[0]:
Queue[No.0] = 2
Queue[No.0] = 3
Queue[No.0] = 3

Queue[1]:
Queue[No.1] = 2
Queue[No.1] = 3
Queue[No.1] = 3

Queue[2]:
Queue[No.2] = 2
Queue[No.2] = 3
Queue[No.2] = 3

Queue[3]:
Queue[No.3] = 2
Queue[No.3] = 3
Queue[No.3] = 3

Queue[4]:
Queue[No.4] = 2
Queue[No.4] = 3
Queue[No.4] = 3

done..!

但是在我更改了 queue 结构中的指针 (currentValue) 使其成为整数类型并编辑函数 popQueue()< 中的一些行之后 一切正常。

--这是编辑后的功能:

int* popQueue(struct queue *Q)
{
  int i;
  if(Q->count > 0)
  {
    Q->currentValue = Q->theQueue[0];
    Q->pointer--;
    Q->count--;

    for(i=0; i < Q->count; i++)
    {
      int* currentPtr = Q->theQueue + i;
      int* nextPtr = currentPtr + 1;
      *currentPtr = *nextPtr;
    }
    return &Q->currentValue;
  }

--这是正确的输出:

Queue[0]:
Queue[No.0] = 1
Queue[No.0] = 2
Queue[No.0] = 3

Queue[1]:
Queue[No.1] = 1
Queue[No.1] = 2
Queue[No.1] = 3

Queue[2]:
Queue[No.2] = 1
Queue[No.2] = 2
Queue[No.2] = 3

Queue[3]:
Queue[No.3] = 1
Queue[No.3] = 2
Queue[No.3] = 3

Queue[4]:
Queue[No.4] = 1
Queue[No.4] = 2
Queue[No.4] = 3

问题是:是什么导致第一个代码提供错误的输出？

Answer 1

在第一种情况下给你错误输出的原因是指针 Q->currentValue从未改变过它的值(它所持有的地址)。它始终指向队列中的第一个元素。

假设队列包含 {1, 2, 3 |,<garbage>} .

这意味着，在第一次弹出之后，队列变成:

{2, 3 |, 3, <garbage>}

和currentValue仍然保存数组中第一个元素的地址，即 2 .

第二次弹出后:

{3 |, 3, 3, <garbage>}

和currentValue指向第一个元素，其值为3 ,

最后一次，数组没有变化(因为 Q->count-- 将 Q->count 的值更改为 0)，所以内容为

{| 3, 3, 3, <garbage>}和currentValue仍然指向 3 .

我假设您将第二个示例更改为 Queue->currentValue一个int .

这样，它保留了原始的第一个元素(已弹出)。

这使得您的打印在测试用例中正常工作。

但是，

• 如果您有 0，您的实现将会失败在您的队列中。
• 您的实现给 pop 增加了不必要的复杂性操作(O(n))。实现一个循环队列会好得多，用 head和tail .
• 保留弹出元素的副本以返回它不是我的第一选择。我建议实现 isEmpty()方法，在 while 中检查其结果循环，当队列不为空时，只需 pop()返回队列前进其 head并返回前一个头元素。