1

我很难尝试实现此方法，因为 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 我不能使用指针算术。

4

3 回答 3

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--;
}
于 2009-04-03T01:52:07.577 回答
0

如果您不使用 STL，则可能需要使用链表。要入队，请添加到列表的末尾。要出队，请从列表的开头删除。为了性能和方便，您应该存储列表两端的指针。

于 2009-04-03T01:50:01.137 回答
0

如果您受限于特定的数组大小，则可以使用普通的 ol' C 数组轻松实现队列。您需要两个指针/索引：队列的开头和队列的结尾。您还需要数组本身。

您可以通过 (1) 包装或 (2) 在到达末尾时复制数组来防止队列溢出。这两种方法都相当简单，但包装更容易、更快捷。使用循环缓冲区调用包装数据元素，并且对于队列和音频缓冲区很常见。

Queue:  0 1 4 3 6 8 0 0 0 0 0
Start:      ^
End:                ^

Dequeue: return 4 (read, then move start to right)
Queue:  0 1 4 3 6 8 0 0 0 0 0
Start:        ^
End:                ^

Enqueue: 9 (write, then move end to right)
Queue:  0 1 4 3 6 8 9 0 0 0 0
Start:        ^
End:                  ^

Wrapping enqueue: 2 (write, then move to right and wrap to beginning)
Queue:  0 1 4 3 6 8 9 3 4 7 2
Start:        ^
End:    ^
于 2009-04-03T01:52:13.690 回答