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.

In your example, what are prov, r, f, and n? Can you post the body of your class? — strager
I'm using a list allocated with list* Object = new Object[10] for example. I need it to work with this. — brsunli
In case this is a programming assignment, please consider finding the answers in your course material instead of taking shortcuts by getting the answer on SO. — lothar

Smashery Smashery · Accepted Answer · 2009-04-03T01:52:07

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

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

3 Answers