Метод enqueue () добавляет один элемент в очередь: как реализовать в 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--;
}

Answer 2

Если вы ограничены определенным размером массива, вы можете легко создать очередь, используя обычный старый 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:    ^

Answer 3

Если вы не используете STL, вы можете использовать связанный список. Чтобы поставить в очередь, добавьте в конец списка. Для удаления из очереди удалите из начала списка. Вы должны хранить указатели для любого конца списка для производительности и удобства.