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.

Practice

1. Which data structure should you use when you want to process tasks in the exact order they arrive, like customers waiting in line at a store?

easy

A. Queue, because it processes elements in First-In-First-Out order

B. Stack, because it processes elements in Last-In-First-Out order

C. Array, because it allows random access

D. Tree, because it organizes data hierarchically

Solution

1. Step 1: Understand the order of processing tasks

   Tasks arriving in order and processed in the same order means First-In-First-Out (FIFO).

2. Step 2: Match FIFO with the correct data structure

   Queue follows FIFO, so it fits the scenario of customers waiting in line.

3. Final Answer:

   Queue, because it processes elements in First-In-First-Out order -> Option A

4. Quick Check:

   FIFO = Queue [OK]

Hint: FIFO means use Queue, like a line of customers [OK]

Common Mistakes:

• Confusing FIFO with LIFO
• Choosing Stack for ordered processing
• Thinking arrays maintain insertion order automatically

2. Which of the following is the correct way to push an element onto a stack in C?

easy

A. push(element, stack);

B. stack.push(element);

C. stack->push(element);

D. push(stack, element);

Solution

1. Step 1: Recall typical C stack function syntax

   In C, stack operations are usually functions taking the stack and element as arguments.

2. Step 2: Identify correct function call order

   push(stack, element) is the standard way to push an element onto a stack in C.

3. Final Answer:

   push(stack, element); -> Option D

4. Quick Check:

   Function call with stack first = push(stack, element) [OK]

Hint: In C, function calls usually have data structure first [OK]

Common Mistakes:

• Using object.method() syntax which is not C style
• Swapping argument order in function call
• Assuming stack is a pointer with methods

3. What will be the output of the following C code snippet using a stack?

#include 
#include 

#define MAX 5

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

void push(Stack *s, int val) {
    if (s->top == MAX - 1) return;
    s->items[++s->top] = val;
}

int pop(Stack *s) {
    if (s->top == -1) return -1;
    return s->items[s->top--];
}

int main() {
    Stack s;
    s.top = -1;
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("%d ", pop(&s));
    printf("%d ", pop(&s));
    return 0;
}

medium

A. 10 20

B. 30 20

C. 20 10

D. 30 10

Solution

1. Step 1: Trace push operations on stack

   Push 10, stack: [10]; push 20, stack: [10,20]; push 30, stack: [10,20,30]. Top points to 30.

2. Step 2: Trace pop operations and output

   First pop returns 30, second pop returns 20, so output is "30 20 ".

3. Final Answer:

   30 20 -> Option B

4. Quick Check:

   LIFO pop order = 30 then 20 [OK]

Hint: Stack pops last pushed first (LIFO) [OK]

Common Mistakes:

• Assuming FIFO order for stack
• Mixing push and pop order
• Ignoring initial top = -1

4. The following C code tries to implement a queue but has a bug. What is the main issue?

#include 
#define MAX 3

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int val) {
    if (rear == MAX - 1) {
        printf("Queue full\n");
        return;
    }
    queue[++rear] = val;
    if (front == -1) front = 0;
}

int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue empty\n");
        return -1;
    }
    return queue[front++];
}

int main() {
    enqueue(1);
    enqueue(2);
    enqueue(3);
    dequeue();
    enqueue(4);
    printf("%d\n", queue[rear]);
    return 0;
}

medium

A. The enqueue function uses wrong index for insertion

B. The dequeue function returns wrong element

C. The queue does not reset front and rear after dequeueing all elements, causing overflow

D. The queue size is too large

Solution

1. Step 1: Understand enqueue and dequeue behavior

   Enqueue adds at rear, dequeue removes from front. After dequeueing all, front > rear but variables not reset.

2. Step 2: Identify problem with overflow after dequeue

   After dequeueing, rear stays at max index, so enqueue thinks queue is full even if space is free.

3. Final Answer:

   The queue does not reset front and rear after dequeueing all elements, causing overflow -> Option C

4. Quick Check:

   Queue pointers not reset = overflow bug [OK]

Hint: Reset front and rear when queue becomes empty [OK]

Common Mistakes:

• Ignoring front and rear reset after emptying queue
• Thinking enqueue index is wrong
• Assuming dequeue returns wrong element

5. You need to design a system that supports undo and redo operations for text editing. Which data structure(s) should you use and why?

hard

A. Two stacks: one for undo and one for redo, because stacks support LIFO order needed for undo/redo

B. One queue, because it processes commands in order

C. One stack only, because redo is not needed

D. Two queues, because they maintain order of commands

Solution

1. Step 1: Understand undo/redo operation order

   Undo reverses last action (LIFO), redo re-applies undone actions in reverse order.

2. Step 2: Choose data structures matching LIFO behavior

   Two stacks allow pushing actions for undo and redo separately, supporting LIFO order for both.

3. Final Answer:

   Two stacks: one for undo and one for redo, because stacks support LIFO order needed for undo/redo -> Option A

4. Quick Check:

   Undo/Redo = Two stacks (LIFO) [OK]

Hint: Undo/Redo needs two stacks for LIFO operations [OK]

Common Mistakes:

• Using queues which are FIFO, not suitable for undo
• Ignoring redo functionality
• Using only one stack which can't handle redo