enqueue() method adds one element to the queue: how to implement in C++?

Question

I'm having a hard time trying to implement this method since array subscripts in C++ start with zero. The method add one element to the queue. You can use f (front) and r (rear) pointers and a sequential list of size n. If you find that additional variables are needed fell free. Thanks.

Thats my try but I know its wrong:

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
    }
}

How do I work with the pointers? If I start them pointing to NULL I cant use pointer arithmetic.

Answer 1

If you're not using STL, you may want to use a linked list. To enqueue, add to the end of the list. To dequeue, remove from the beginning of the list. You should store pointers for either end of the list for performance and convenience.

Answer 2

To implement a queue using plain arrays, just treat it circularly - so as soon as you run out of space in the array, wrap back around to 0. You'll need to keep a record of front and rear, as you note. As an example (where X represents an item in the queue):

// 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

You just have to use modular arithmetic to wrap around. Of course, this is limited in size (once you run out of elements, you'd have to allocate more memory), but that's just what you get when dealing with arrays.

Here's some code as a start (I haven't checked it at all):

// 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 3

If you're restricted to a specific array size, you can implement a queue easily using a plain ol' C array. You need two pointers/indexes: the beginning of the queue and the end of the queue. You also need the array itself.

You can prevent your queue from overflowing by either (1) wrapping, or (2) copying the array when you reach the end. Either method is rather trivial, but wrapping is easier and faster. Wrapping your data elements is called using a circular buffer, and is common for queues and audio buffers.

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:    ^