Following is C like pseudo code of a function that takes a Queue as an…

2026

Following is C like pseudo code of a function that takes a Queue as an argument, and uses a stack S to do processing.

void fun(Queue *Q)
{
    Stack S;  // Say it creates an empty stack S

    // Run while Q is not empty
    while (!isEmpty(Q))
    {
        // deQueue an item from Q and push the dequeued item to S
        push(&S, deQueue(Q));
    }

    // Run while Stack S is not empty
    while (!isEmpty(&S))
    {
        // Pop an item from S and enqueue the popped item to Q
        enQueue(Q, pop(&S));
    }
}

What does the above function do in general?

  1. A.

    Removes the last element from Q

  2. B.

    Keeps the Q same as it was before the call

  3. C.

    Makes Q empty

  4. D.

    Reverses the Q

Show answer & explanation

Correct answer: D

Concept:

A queue is FIFO (first element in is the first one out) while a stack is LIFO (last element in is the first one out). Whenever every element of a sequence is moved through a stack and then moved back out, the traversal order comes out completely flipped, because the item that entered the stack last is always the one that leaves it first.

Application:

  1. First loop: while Q is not empty, dequeue its front item and push it onto S. Since dequeue always takes the current front, the item originally at the front of Q is pushed FIRST, so it ends up at the BOTTOM of S; the item originally at the back of Q is pushed LAST, so it ends up at the TOP of S.

  2. Second loop: while S is not empty, pop its top item and enqueue it into Q. Pop always removes the current top, so the item at the top of S (originally the back of Q) is enqueued FIRST, and the item at the bottom of S (originally the front of Q) is enqueued LAST.

  3. So the item that used to be at the front of Q is now enqueued last (goes to the new back), and the item that used to be at the back of Q is now enqueued first (goes to the new front) — the entire front-to-back order of Q has been flipped.

Cross-check:

Trace Q = [1, 2, 3, 4] (front = 1, back = 4). First loop dequeues 1, 2, 3, 4 in that order and pushes each onto S, so S from top to bottom is [4, 3, 2, 1]. Second loop pops 4, 3, 2, 1 in that order and enqueues each into Q, so Q becomes [4, 3, 2, 1] from front to back — the exact reverse of the original [1, 2, 3, 4].

So the function reverses the order of the elements in Q.

Explore the full course: Coding For Placement