Question

Describe in pseudo-code, a linear-time algorithm for reversing a queue Q. To access the queue, you are only allowed to use the basic functions of the queue ADT defined as follows

(Hint: Using a stack, the basic stack functions defined in the textbook and in the class).

class Queue {

public: int size();

bool isEmpty();

Object front();

void enqueue(Object o);

Object dequeue();

};

Answer 1

We will use stack for this purpose. We will:

1) Dequeue the complete queue and insert the elements into stack

2) Pop all the elements from the stack and enqueue them into queue again.

It will take O(n) time to dequeue n elements from queue and to add them to stack. And it will again take O(n) time to pop all the elements from stack and enqueue them again to queue.

Overall time complexity = O(n) + O(n) = O(2n) = O(n), which is a linear time complexity.

Pseudocode for this algorithm is:

REVERSE(Queue q){
    
    CREATE a stack s;

    //Dequeue all the elements from queue and insert them to a stack
    while q is not empty{
        elem = q.dequeue()
        
        //push that dequeued value to stack s
        s.push(elem);
    }

    //now pop all elements from stack and enqueue them to q again
    while s is not empty{
        elem = s.pop()
        
        //enqueue that element to q
        q.enqueue(elem);
    }

    RETURN q;
}

If this helps you, do upvote as it motivates us a lot!