One of the most interesting thoughts about Queue implementat

One of the most interesting thoughts about Queue implementations is how we can get good O(1) performance by being a little clever and using the array like a clock. While you do not need to complete a full Queue implementation, you should understand how to code this clock-like work. on the following which has three methods for you to complete:

enqueueUpdateIndex() -- assume an array has a length of arrayLength and update the instance variable\'s as if we added an element to the queue

dequeueUpdateIndex() -- assume an array has a length of arrayLength and update the instance variable\'s as if we removed an element from the queue

dequeueUpdateIndex() -- return if the array has as many elements as it can handle when used in this matter

Code:

Solution

4

3

2

1

Rear

0

Front

In above figure of Queue

arrayLength = 5 , Front=0 , Rear=1;

            When we reach Rear=4 then for addition we have to again start from 0 if queue is not full(i.e. If we remove the (dequeue) the element from queue in between) .

So here we are doing              

Rear = (Rear+1) % arrayLength;

We have to first update the Front and then we have to dequeue element

So If we reach Front = 4 we have to start from 0

So Front = (Front+1) % arrayLength.

So in this we have to check Front == Rear ; because if both meets then that indicate Queue is full.

During Enqueue we have to check for Full condition because if Queue is full then we can dequeue but cannot Enqueue the element.

So

(Rear+1)%arrayLenth == Front

If Above condition is true then queue is full otherwise not.

Below is the code modification

# include<iostream>

using namespace std;

class ArrayQueueIndices

    private:

        int Front;   // The index at which the first element in the queue would be stored.

        int Rear;   // The index just after the one at which the most recently added element in the queue would be stored.

       /*

        The mythical array or list length for this class. Since we are not worrying about implementating Queue, we do not

        worry about the actual array or list.

        */

        int arrayLength;

    public:

        //Create a new (empty) instance of this class.

        ArrayQueueIndices()

        {

            Front = 0;

            Rear = 1;

            arrayLength = 16;

        }

        /*

            Called when a new element was added to the end of the queue. We will assume that there is space for this element

            and so can just update the instance variables appropriately.

        */

        void enqueueUpdateIndex()

        {

            Rear = (Rear+1)%arrayLength;

        }

        /*

            Called when a new element was removed from the front of the queue. We will assume that there was an element in the

            queue and so can just update the instance variables appropriately.

        */

        void dequeueUpdateIndex()

        {

            Front = (Front+1)%arrayLength;

        }

        /*

            Called to check if the front and rear values indicate that a larger array or list is needed. Since we are not

            worrying about implementation, we just return if it is needed and do not actually do anything about it.

        */

        bool isFull();

        {

            return (Rear+1)%arrayLength == Front?true:false;

        }

};

4
3
2
1	Rear
0	Front