Queue and Stack behavior in C Sharp (C#) - Time & Space Complexity

Time Complexity: Queue and Stack behavior

O(n)

Understanding Time Complexity

We want to understand how the time it takes to add or remove items from queues and stacks changes as we add more items.

How does the number of operations grow when we use these data structures?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

Queue<int> queue = new Queue<int>();
Stack<int> stack = new Stack<int>();

// Add 1000 items
for (int i = 0; i < 1000; i++) {
    queue.Enqueue(i);
    stack.Push(i);
}

// Remove all items
while (queue.Count > 0) {
    queue.Dequeue();
}
while (stack.Count > 0) {
    stack.Pop();
}
    

This code adds 1000 items to both a queue and a stack, then removes all items from each.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding and removing items one by one in loops.
• How many times: Each loop runs 1000 times for adding, then 1000 times for removing.

How Execution Grows With Input

When we add or remove more items, the total operations increase directly with the number of items.

Input Size (n)	Approx. Operations
10	About 20 operations (10 adds + 10 removes)
100	About 200 operations (100 adds + 100 removes)
1000	About 2000 operations (1000 adds + 1000 removes)

Pattern observation: The total work grows in a straight line as input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to add and remove items grows directly in proportion to how many items there are.

Common Mistake

[X] Wrong: "Removing an item from a queue or stack takes longer as the queue or stack gets bigger."

[OK] Correct: Both queue and stack remove items from one end only, so each remove operation takes the same short time no matter the size.

Interview Connect

Understanding how queues and stacks work with time helps you explain why these structures are efficient for certain tasks, a skill valued in many coding challenges.

Self-Check

"What if we used a list and removed items from the front instead of a queue? How would the time complexity change?"