Queue Using Two Stacks in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of enqueue and dequeue operations

What is the printed state of the queue after performing these operations using two stacks?

Operations:
enqueue(1), enqueue(2), dequeue(), enqueue(3), dequeue(), enqueue(4), dequeue()

DSA C

struct Stack {
    int arr[10];
    int top;
};

struct Queue {
    struct Stack s1, s2;
};

void push(struct Stack* s, int val) {
    s->arr[++s->top] = val;
}

int pop(struct Stack* s) {
    return s->arr[s->top--];
}

int isEmpty(struct Stack* s) {
    return s->top == -1;
}

void enqueue(struct Queue* q, int val) {
    push(&q->s1, val);
}

int dequeue(struct Queue* q) {
    if (isEmpty(&q->s2)) {
        while (!isEmpty(&q->s1)) {
            push(&q->s2, pop(&q->s1));
        }
    }
    return pop(&q->s2);
}

void printQueue(struct Queue* q) {
    // Print elements in s2 from top to bottom
    for (int i = q->s2.top; i >= 0; i--) {
        printf("%d -> ", q->s2.arr[i]);
    }
    // Print elements in s1 from bottom to top
    for (int i = 0; i <= q->s1.top; i++) {
        printf("%d -> ", q->s1.arr[i]);
    }
    printf("null\n");
}

int main() {
    struct Queue q = {{}, -1, {}, -1};
    enqueue(&q, 1);
    enqueue(&q, 2);
    dequeue(&q);
    enqueue(&q, 3);
    dequeue(&q);
    enqueue(&q, 4);
    dequeue(&q);
    printQueue(&q);
    return 0;
}

A 3 -> 4 -> null

B 4 -> null

C 2 -> 3 -> 4 -> null

D 1 -> 3 -> 4 -> null

💡 Hint

Remember dequeue moves elements from s1 to s2 only when s2 is empty.

After the operations, the queue contains element 4. The dequeue operations remove 1, then 2, then 3, leaving 4 in the queue. The printQueue function prints s2 top to bottom then s1 bottom to top, resulting in '4 -> null'.

🧠 Conceptual

intermediate

Understanding the dequeue operation in two stacks queue

Why does the dequeue operation transfer elements from the first stack to the second stack only when the second stack is empty?

A To reverse the order of elements so the oldest element is on top for dequeue

B To save memory by not using the second stack unnecessarily

C To sort the elements in ascending order before dequeue

D To avoid pushing new elements during dequeue

💡 Hint

Think about how stacks work and the order of elements.

The first stack stores elements in order of insertion. Transferring all elements to the second stack reverses their order, making the oldest element accessible at the top for dequeue. This simulates queue behavior using stacks.

🔧 Debug

advanced

Identify the error in this dequeue implementation

What error will this dequeue function cause when called on an empty queue?

DSA C

int dequeue(struct Queue* q) {
    if (isEmpty(&q->s2)) {
        while (!isEmpty(&q->s1)) {
            push(&q->s2, pop(&q->s1));
        }
    }
    return pop(&q->s2);
}

A Runtime error due to popping from empty stack

B Syntax error due to missing return statement

C Logical error returning wrong element

D No error, works correctly

💡 Hint

What happens if both stacks are empty?

If both stacks are empty, pop(&q->s2) tries to remove an element from an empty stack, causing a runtime error (underflow). The code does not check if the queue is empty before popping.

📝 Syntax

advanced

Identify the syntax error in this enqueue function

Which option correctly fixes the syntax error in this enqueue function?

DSA C

void enqueue(struct Queue* q, int val) {
    push(&q->s1 val);
}

A push(&q->s1.val);

B push(q->s1, val);

C push(&q->s1, val);

D push(q->s1.val);

💡 Hint

Check the syntax of function arguments and pointer usage.

The push function requires a pointer to the stack and the value. The correct syntax uses a comma between arguments and '&' to pass the address.

🚀 Application

expert

Calculate the number of elements after mixed operations

Given an initially empty queue implemented with two stacks, after performing these operations:
enqueue(5), enqueue(10), dequeue(), enqueue(15), enqueue(20), dequeue(), dequeue(), enqueue(25)
How many elements remain in the queue?

A 1

B 4

C 3

D 2

💡 Hint

Track each operation step-by-step and count remaining elements.

The operations enqueue 5, 10, 15, 20, 25 (5 elements) and dequeue 3 times, removing 5, 10, 15, leaving 20 and 25 (2 elements).