Implement Stack Using Queue in DSA C - Time & Space Complexity

Time Complexity: Implement Stack Using Queue

O(n)

Understanding Time Complexity

We want to understand how the time taken changes when we use a queue to build a stack.

Specifically, how the operations like push and pop grow as we add more items.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

#define MAX 100

int queue[MAX];
int front = 0, rear = 0;

void enqueue(int x) {
    queue[rear++] = x;
}

int dequeue() {
    return queue[front++];
}

void push(int x) {
    int size = rear - front;
    enqueue(x);
    for (int i = 0; i < size; i++) {
        enqueue(dequeue());
    }
}

int pop() {
    if (front == rear) return -1; // empty
    return dequeue();
}

int main() {
    push(1);
    push(2);
    push(3);
    printf("%d ", pop());
    printf("%d ", pop());
    return 0;
}
    

This code uses one queue to simulate a stack by rearranging elements on each push.

Identify Repeating Operations

• Primary operation: The for-loop inside the push function that moves existing elements.
• How many times: It runs once for each element already in the queue before adding the new one.

How Execution Grows With Input

Each push moves all existing elements to keep the newest element at the front.

Input Size (n)	Approx. Operations in push
10	About 10 moves
100	About 100 moves
1000	About 1000 moves

Pattern observation: The number of moves grows linearly with the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means pushing an element takes time proportional to how many elements are already in the stack.

Common Mistake

[X] Wrong: "Push operation is always O(1) because we just add one element."

[OK] Correct: Here, push rearranges all existing elements, so it takes longer as the stack grows.

Interview Connect

Understanding how to build one data structure using another shows your problem-solving skills and helps you think about efficiency.

Self-Check

"What if we used two queues instead of one? How would that change the time complexity of push and pop?"