Queue Using Two Stacks in DSA C

Mental Model

Use two stacks to mimic the behavior of a queue by reversing order twice.

Analogy: Imagine two trays where you put plates in one tray stacked on top, then move them to the second tray to reverse order, so you can take plates out in the order they were put in.

stack1: top -> [3] [2] [1]
stack2: top -> [1] [2] [3]
queue front is at bottom of stack1 but accessible via stack2 after transfer

Dry Run Walkthrough

Input: enqueue 1, enqueue 2, enqueue 3, dequeue, enqueue 4, dequeue

Goal: Show how two stacks work together to enqueue and dequeue in FIFO order

Step 1: enqueue 1: push 1 onto stack1

stack1: [1]
stack2: []

Why: New elements go into stack1 to keep insertion order

Step 2: enqueue 2: push 2 onto stack1

stack1: [2, 1]
stack2: []

Why: Keep adding new elements on top of stack1

Step 3: enqueue 3: push 3 onto stack1

stack1: [3, 2, 1]
stack2: []

Why: Stack1 holds all new elements in order

Step 4: dequeue: stack2 empty, move all from stack1 to stack2 reversing order

stack1: []
stack2: [1, 2, 3]

Why: Reversing stack1 into stack2 makes oldest element accessible on top

Step 5: dequeue: pop top of stack2 (1)

stack1: []
stack2: [2, 3]

Why: Remove oldest element from queue

Step 6: enqueue 4: push 4 onto stack1

stack1: [4]
stack2: [2, 3]

Why: New elements always go to stack1

Step 7: dequeue: pop top of stack2 (2)

stack1: [4]
stack2: [3]

Why: Continue removing from stack2 until empty

Result:

stack1: [4]
stack2: [3]
Dequeued elements in order: 1, 2

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct Stack {
    int arr[MAX];
    int top;
} Stack;

void initStack(Stack* s) {
    s->top = -1;
}

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

int isFull(Stack* s) {
    return s->top == MAX - 1;
}

void push(Stack* s, int val) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->arr[++(s->top)] = val;
}

int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

typedef struct Queue {
    Stack s1;
    Stack s2;
} Queue;

void initQueue(Queue* q) {
    initStack(&q->s1);
    initStack(&q->s2);
}

void enqueue(Queue* q, int val) {
    push(&q->s1, val); // push new element onto s1
}

int dequeue(Queue* q) {
    if (isEmpty(&q->s2)) { // if s2 empty, move all from s1 to s2
        while (!isEmpty(&q->s1)) {
            int x = pop(&q->s1); // pop from s1
            push(&q->s2, x);     // push onto s2
        }
    }
    return pop(&q->s2); // pop from s2 is dequeue
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);

    printf("Dequeued: %d\n", dequeue(&q));

    enqueue(&q, 4);

    printf("Dequeued: %d\n", dequeue(&q));

    return 0;
}

push(&q->s1, val); // push new element onto s1

add new element to stack1 to keep insertion order

if (isEmpty(&q->s2)) { while (!isEmpty(&q->s1)) { int x = pop(&q->s1); push(&q->s2, x); } }

transfer all elements from stack1 to stack2 to reverse order when stack2 empty

return pop(&q->s2); // pop from s2 is dequeue

remove and return the oldest element from stack2

Output

Dequeued: 1

Dequeued: 2

Complexity Analysis

Time: O(1) amortized for enqueue and dequeue because each element is moved at most twice between stacks

Space: O(n) because all elements are stored in two stacks combined

vs Alternative: Compared to a linked list queue with O(1) enqueue and dequeue, this uses two stacks and may have occasional O(n) transfer but amortized O(1)

Edge Cases

dequeue from empty queue

returns -1 and prints underflow message

DSA C

if (isEmpty(&q->s2)) { ... } return pop(&q->s2);

enqueue after some dequeues

new elements go to stack1 without affecting stack2 until stack2 empties

DSA C

push(&q->s1, val);

all elements dequeued, then enqueue new elements

stack2 empty triggers transfer from stack1 on next dequeue

DSA C

if (isEmpty(&q->s2)) { while (!isEmpty(&q->s1)) { ... } }

When to Use This Pattern

When you need to implement a queue but only have stack operations, use two stacks to reverse order twice and simulate FIFO behavior.

Common Mistakes

Mistake: Trying to dequeue directly from stack1 without transferring to stack2
Fix: Always transfer elements from stack1 to stack2 when stack2 is empty before dequeue

Mistake: Transferring elements from stack1 to stack2 on every dequeue
Fix: Only transfer when stack2 is empty to keep amortized O(1) complexity

Summary

Implements a queue using two stacks by reversing element order twice.

Use when only stack operations are allowed but queue behavior is needed.

The key is transferring elements from one stack to another only when needed to maintain correct order.