c++ - enqueue() 方法向队列 : how to implement in C++? 添加一个元素

Question

我很难尝试实现此方法，因为 C++ 中的数组下标从零开始。该方法向队列中添加一个元素。您可以使用 f(前)和 r(后)指针以及大小为 n 的顺序列表。如果您发现需要额外的变量，请放弃。谢谢。

那是我的尝试，但我知道这是错误的:

void QueueAr::enqueue(const Object& x){
    prov = (r % n) + 1;
    if(prov != f){
        r = prov;
        queueArray[r] = x;
        if(f = -1){
            f = 0
        }
    }else{
        //queue is full
    }
}

如何使用指针？如果我开始将它们指向 NULL，我将无法使用指针算法。

Answer 1

要使用普通数组实现队列，只需循环处理它 - 所以一旦数组中的空间用完，就回绕到 0。你需要记录前后，因为你笔记。例如(其中 X 代表队列中的一个项目):

// Rear is where to enqueue into, Front is where to dequeue from
Empty Array:
| - - - |
Front = -1, Rear = 0 

Enqueue()
| X - - |
Front = 0, Rear = 1

Enqueue()
| X X - |
Front = 0, Rear = 2

Dequeue()
| - X - |
Front = 1, Rear = 2

Enqueue()
| - X X |
Front = 1, Rear = 0 // Looped around

Dequeue()
| - - X |
Front = 2, Rear = 0

Enqueue()
| X - X |
Front = 2, Rear = 1

你只需要使用模块化算法来环绕。当然，这在大小上是有限的(一旦用完元素，就必须分配更多内存)，但这正是处理数组时得到的结果。

这里有一些代码作为开始(我根本没有检查过):

// Private class variables:
// These should be set in the constructor of your queue class
unsigned int rear = 0; // back of the queue
unsigned int front = -1; // front of the queue
unsigned int numStored = 0;
unsigned int length;
Object* array = new Object[length];

QueueAr::Enqueue(Object& obj)
{
    if (front == rear)
    {
        // Throw an exception: queue is full!
    }
    else
    {
        array[rear] = obj; // Insert the object at the back
        rear++;
        rear = rear % length;
        numStored++;
    }
}
// For kicks, here's the queue code
QueueAr::Dequeue(Object& obj)
{
    if (numStored == 0)
    {
        // Throw an exception: queue is empty!
    }
    front++;
    front = front % length;
    numStored--;
}