Implement all the 4 public methods of the Queue class. (isEmpty, isFull and enqueue should be of complexity O(1) and dequeue should be of complexity O(n).)

QUESTION                                                                                    

Suppose we are given the following specification for a Stack class of integers:

Class Stack

{

     public:

       Stack();   

       //allocates sufficient memory to stack

       ~Stack();

       //deallocates memory               

bool isEmpty( );

       //   return true if stack is empty 

bool isFull( );

// return true if stack is full    

bool push(int x);

// push x on the stack, return true if successful else return false

bool pop(int &x);

// pops from stack into x, returns true if successful else returns      //false

};

Two instances of this class are used to implement a Queue of integers.  Implement all the 4 public methods of the Queue class. (The partial definition of this class is given below.) . 

IMPORTANT: isEmpty, isFull and enqueue should be of complexity O(1) and dequeue should be of complexity O(n). 

(Note: You are not to implement the Stack class methods or make any changes to its class. Also, you may assume that the arrays used to implement the two stacks in the definition of class Stack are of the same size.)

           

Class Queue

{

     public:

bool enqueue(int x); 

/* inserts value x in the queue, returns true if successful else returns false */

bool dequeue(int &x);

/* removes integer from queue,returns true if successful else returns false */

bool isEmpty();

/* return true if queue is empty */

bool isFull();

/* return true if queue is full */

     private:

        Stack S1, S2;

        /* you are not allowed to use any other private members */

};

SOLUTION

NOTE:  This is not the only solution.  You can definitely give a better solution.

Here we will put an item on S1 when we want to enqueue an item.  This will be O(1).  When dequeueing, we will have to pop all the elements on S2, take out the last item on S2 and place in x (as it was the first item enqueued) and place all the remaining elements back on S1.  This will be O(n).  This is because stack is LIFO and queue is FIFO.  As we are placing all items on S1 all the time and S2 is just used for temporary storage, the queue will be full when S1 is full and queue will be empty when S1 is empty.

bool Queue::enqueue(int x)

{

            //check if queue is full

            bool toReturn = false;

            if (! IsFull() )

                        toReturn = S1.push(x);                        //put x on stack 1

            return toReturn;

           

}

bool Queue::dequeue(int &x)

{          //proceed only if queue is not empty

            bool returnValue = false;

            if (! IsEmpty() )

            {          //now shift all items from S1 to S2

            int temp;

            while ( !S1.IsEmpty() )

            {

                        S1.pop(temp);

                        S2.push(temp);

            }

            //take out the last item on S2 as it is the dequeued item

            S2.pop(x);

            //now shift all items from S2 to S1

            while ( !S2.IsEmpty() )

            {

                        S2.pop(temp);

                        S1.push(temp);

            }

            returnValue  = true;

}

return returnValue;

}

//queue is full when S1 is full bool Queue::IsFull() {             return S1.IsFull(); }

//queue is empty when S1 is empty bool Queue::IsEmpty() {             return S1.IsEmpty(); }