Queue vs Stack When to Use Which in DSA C - Trade-offs & Analysis

Mental Model

A stack works like a stack of plates where you add and remove from the top. A queue works like a line where the first person in line is served first.

Analogy: Imagine a stack as a pile of books where you can only add or remove the top book. A queue is like a line at a ticket counter where the first person to join the line is the first to get the ticket.

Stack (top at right): bottom -> 1 -> 2 -> 3 [top]
Queue (front at left): [front] 1 -> 2 -> 3 -> rear

Dry Run Walkthrough

Input: Stack: push 1, push 2, pop; Queue: enqueue 1, enqueue 2, dequeue

Goal: Show how stack and queue add and remove elements differently

Step 1: Push 1 onto stack

Stack: bottom -> 1 [top]
Queue: empty

Why: Add first element to stack at the top

Step 2: Push 2 onto stack

Stack: bottom -> 1 -> 2 [top]
Queue: empty

Why: Add second element on top of first in stack

Step 3: Pop from stack

Stack: bottom -> 1 [top]
Queue: empty

Why: Remove the top element (2) from stack

Step 4: Enqueue 1 into queue

Stack: bottom -> 1 [top]
Queue: [front] 1 -> rear

Why: Add first element to rear of queue

Step 5: Enqueue 2 into queue

Stack: bottom -> 1 [top]
Queue: [front] 1 -> 2 -> rear

Why: Add second element to rear of queue

Step 6: Dequeue from queue

Stack: bottom -> 1 [top]
Queue: [front] 2 -> rear

Why: Remove the front element (1) from queue

Result:

Stack final: bottom -> 1 [top]
Queue final: [front] 2 -> rear

Annotated Code

DSA C

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

#define MAX 10

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

typedef struct {
    int arr[MAX];
    int front;
    int rear;
} Queue;

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

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

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

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

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

void queue_init(Queue* q) {
    q->front = 0;
    q->rear = -1;
}

int queue_is_empty(Queue* q) {
    return q->rear < q->front;
}

int queue_is_full(Queue* q) {
    return q->rear == MAX - 1;
}

void queue_enqueue(Queue* q, int val) {
    if (queue_is_full(q)) {
        printf("Queue overflow\n");
        return;
    }
    q->arr[++q->rear] = val; // add val at rear
}

int queue_dequeue(Queue* q) {
    if (queue_is_empty(q)) {
        printf("Queue underflow\n");
        return -1;
    }
    return q->arr[q->front++]; // remove val from front
}

void print_stack(Stack* s) {
    printf("Stack (bottom to top): ");
    for (int i = 0; i <= s->top; i++) {
        printf("%d ", s->arr[i]);
    }
    printf("\n");
}

void print_queue(Queue* q) {
    printf("Queue (front to rear): ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->arr[i]);
    }
    printf("\n");
}

int main() {
    Stack s;
    Queue q;

    stack_init(&s);
    queue_init(&q);

    // Stack operations
    stack_push(&s, 1);
    stack_push(&s, 2);
    int popped = stack_pop(&s);

    // Queue operations
    queue_enqueue(&q, 1);
    queue_enqueue(&q, 2);
    int dequeued = queue_dequeue(&q);

    print_stack(&s);
    print_queue(&q);

    return 0;
}

s->arr[++s->top] = val; // push val on top

add element on top of stack

return s->arr[s->top--]; // pop top val

remove element from top of stack

q->arr[++q->rear] = val; // add val at rear

add element at rear of queue

return q->arr[q->front++]; // remove val from front

remove element from front of queue

Output

Stack (bottom to top): 1 

Queue (front to rear): 2 

Complexity Analysis

Time: O(1) for both push/pop in stack and enqueue/dequeue in queue because each operation changes only one end.

Space: O(n) for both because they store up to n elements in an array.

vs Alternative: Compared to using linked lists, arrays are simpler but fixed size; linked lists allow dynamic size but need extra memory for pointers.

Edge Cases

Empty stack pop

Prints 'Stack underflow' and returns -1

DSA C

if (stack_is_empty(s)) { printf("Stack underflow\n"); return -1; }

Empty queue dequeue

Prints 'Queue underflow' and returns -1

DSA C

if (queue_is_empty(q)) { printf("Queue underflow\n"); return -1; }

Full stack push

Prints 'Stack overflow' and does not add element

DSA C

if (stack_is_full(s)) { printf("Stack overflow\n"); return; }

Full queue enqueue

Prints 'Queue overflow' and does not add element

DSA C

if (queue_is_full(q)) { printf("Queue overflow\n"); return; }

When to Use This Pattern

When a problem needs last-in-first-out order, use a stack; when it needs first-in-first-out order, use a queue.

Common Mistakes

Mistake: Using stack pop to remove the oldest element instead of the newest.
Fix: Remember stack removes from the top (last added), not the bottom.

Mistake: Using queue dequeue to remove the newest element instead of the oldest.
Fix: Remember queue removes from the front (first added), not the rear.

Summary

Stack adds and removes elements from the top; queue adds at rear and removes from front.

Use stack when you want to reverse order or track recent items; use queue when order matters and you want to process items in arrival order.

The key insight is stack is last-in-first-out, queue is first-in-first-out.