Queue vs Stack When to Use Which in DSA C - Complexity Comparison

Time Complexity: Queue vs Stack When to Use Which

O(n)

Understanding Time Complexity

We want to understand how the time it takes to use a queue or a stack changes as we add more items.

Which one is faster or better for certain tasks?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple stack push and pop
void stackOperations(int n) {
    int stack[n];
    int top = -1;
    for (int i = 0; i < n; i++) {
        stack[++top] = i; // push operation
    }
    while (top >= 0) {
        int val = stack[top--]; // pop operation
    }
}

// Simple queue enqueue and dequeue
void queueOperations(int n) {
    int queue[n];
    int front = 0, rear = -1;
    for (int i = 0; i < n; i++) {
        queue[++rear] = i; // enqueue operation
    }
    while (front <= rear) {
        int val = queue[front++]; // dequeue operation
    }
}
    

This code shows basic push/pop for stack and enqueue/dequeue for queue with n items.

Identify Repeating Operations

Both stack and queue perform repeated operations:

• Primary operation: push and pop for stack; enqueue and dequeue for queue.
• How many times: Each operation runs exactly n times, once per item.

How Execution Grows With Input

As the number of items n grows, the total operations grow in a straight line.

Input Size (n)	Approx. Operations
10	20 (10 pushes + 10 pops)
100	200 (100 pushes + 100 pops)
1000	2000 (1000 pushes + 1000 pops)

Pattern observation: Operations increase directly with n, doubling because each item is added and then removed.

Final Time Complexity

Time Complexity: O(n)

This means the time to process all items grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Stacks or queues take longer time as they get bigger because of complex operations inside."

[OK] Correct: Both stack and queue operations here are simple and happen once per item, so time grows linearly, not more.

Interview Connect

Understanding when to use stack or queue and their time costs helps you choose the right tool for problems and explain your choices clearly.

Self-Check

"What if we used a linked list instead of an array for the queue? How would the time complexity change?"