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

Time Complexity: Queue vs Stack When to Use Which

O(1) for stack push/pop and queue enqueue; O(n) for queue dequeue using array shift

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 for adding and removing items, and why?

Scenario Under Consideration

Analyze the time complexity of adding and removing items in a queue and a stack.

class Stack {
  private items: number[] = [];
  push(item: number) { this.items.push(item); }
  pop() { return this.items.pop(); }
}

class Queue {
  private items: number[] = [];
  enqueue(item: number) { this.items.push(item); }
  dequeue() { return this.items.shift(); }
}
    

This code shows how we add and remove items in a stack and a queue using arrays.

Identify Repeating Operations

Look at the main actions repeated when using these structures.

• Primary operation: Adding (push/enqueue) and removing (pop/dequeue) items.
• How many times: Each operation happens once per item added or removed.

How Execution Grows With Input

Stack push/pop and queue enqueue take about the same time no matter how many items are inside. Queue dequeue does not.

Input Size (n)	Approx. Operations
10	Stack: 10 adds + 10 removes, each O(1). Queue: 10 enqueues O(1), 10 dequeues O(n)
100	Stack: 100 adds + 100 removes, each O(1). Queue: 100 enqueues O(1), 100 dequeues O(n)
1000	Stack: 1000 adds + 1000 removes, each O(1). Queue: 1000 enqueues O(1), 1000 dequeues O(n)

Pattern observation: Time per stack operation and queue enqueue is constant O(1); queue dequeue is linear O(n). Total time for n operations is O(n) for stack, O(n²) for queue dequeues.

Final Time Complexity

Time Complexity: O(1) for stack push/pop and queue enqueue; O(n) for queue dequeue using array shift

Adding or removing items in a stack is always quick; removing from a queue can be slower if using arrays this way.

Common Mistake

[X] Wrong: "Removing an item from a queue is always as fast as from a stack."

[OK] Correct: Removing from the front of an array (queue dequeue) takes longer because all other items must move, unlike stack pop which removes from the end quickly.

Interview Connect

Knowing when stack or queue operations are fast helps you choose the right tool and explain your choices clearly in interviews.

Self-Check

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

Practice

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

easy

A. Stack

B. Queue

C. Array

D. Tree

Solution

1. Step 1: Understand the order requirement

   Tasks must be processed in the order they arrive, which means first-in, first-out (FIFO).

2. Step 2: Match the data structure to FIFO

   A queue follows FIFO, so it fits the requirement perfectly.

3. Final Answer:

   Queue -> Option B

4. Quick Check:

   FIFO = Queue [OK]

Hint: Use queue for first-in, first-out order [OK]

Common Mistakes:

• Confusing stack (LIFO) with queue (FIFO)
• Choosing array without order guarantees
• Thinking tree fits linear order

2. Which of the following is the correct TypeScript syntax to add an element to the top of a stack implemented as an array named stack?

easy

A. stack.unshift(element);

B. stack.pop(element);

C. stack.shift(element);

D. stack.push(element);

Solution

1. Step 1: Identify stack operation to add element

   Adding to the top of a stack means pushing an element onto it.

2. Step 2: Match with correct array method

   In TypeScript, push() adds an element to the end (top) of the array acting as a stack.

3. Final Answer:

   stack.push(element); -> Option D

4. Quick Check:

   Push adds to stack top [OK]

Hint: Use push() to add on stack top [OK]

Common Mistakes:

• Using pop() which removes instead of adds
• Using shift() or unshift() which affect queue ends
• Confusing push() with unshift()

3. What will be the output of the following TypeScript code?

const queue: number[] = [];
queue.push(1);
queue.push(2);
queue.push(3);
const first = queue.shift();
console.log(queue);

medium

A. [3, 2]

B. [1, 2, 3]

C. [2, 3]

D. []

Solution

1. Step 1: Trace queue operations

   Elements 1, 2, 3 are added to the queue using push(). Then shift() removes the first element (1).

2. Step 2: Determine queue state after removal

   After removing 1, the queue contains [2, 3].

3. Final Answer:

   [2, 3] -> Option C

4. Quick Check:

   shift() removes first, queue left with [2, 3] [OK]

Hint: shift() removes front in queue [OK]

Common Mistakes:

• Thinking push adds to front instead of back
• Confusing shift() with pop()
• Expecting stack order instead of queue order

4. The following TypeScript code is intended to implement a stack but has a bug. What is the bug?

const stack: number[] = [];
stack.push(10);
stack.push(20);
const top = stack.shift();
console.log(top);

medium

A. Using shift() instead of pop() to remove top element

B. Using push() instead of unshift() to add element

C. Not initializing the stack array

D. Using console.log incorrectly

Solution

1. Step 1: Identify stack removal method

   Stack removes the top element using pop(), not shift().

2. Step 2: Analyze code's removal method

   The code uses shift(), which removes the first element, breaking stack behavior.

3. Final Answer:

   Using shift() instead of pop() to remove top element -> Option A

4. Quick Check:

   Stack removal = pop(), not shift() [OK]

Hint: Stack removes top with pop(), not shift() [OK]

Common Mistakes:

• Confusing shift() with pop()
• Thinking push() adds to front
• Ignoring array initialization

5. You are designing a system to undo and redo user actions. Which data structure combination is best suited for this, and why?

hard

A. Two stacks: one for undo, one for redo, because stacks allow reversing actions easily

B. Two queues: one for undo, one for redo, because queues maintain order of actions

C. One stack only, because redo is not needed

D. One queue only, because undo and redo are processed in order

Solution

1. Step 1: Understand undo/redo requirements

   Undo and redo require reversing and reapplying actions in last-in, first-out order.

2. Step 2: Match data structures to behavior

   Stacks naturally support LIFO, so using two stacks (undo and redo) allows easy push/pop for these operations.

3. Final Answer:

   Two stacks: one for undo, one for redo, because stacks allow reversing actions easily -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Using queues which do not reverse order easily
• Ignoring redo functionality
• Using only one data structure