Complexity Analysis

Implementation	Enqueue	Dequeue	Peek	Space	Notes
Library (Deque)	$O(1)$	$O(1)$	$O(1)$	$O(N)$	Highly optimized. Python uses Linked List blocks; Rust uses Ring Buffer.
Circular Queue	$O(1)$	$O(1)$	$O(1)$	$O(K)$	Strict $O(1)$. No memory allocation overhead during runtime. Fixed size $K$.
Queue using Stacks	$O(1)$	Amortized $O(1)$	Amortized $O(1)$	$O(N)$	Worst case for a single dequeue is $O(N)$, but average is $O(1)$.

Detailed

1. Library & Circular Queue (Strict $O(1)$)

These implementations track the head and tail pointers/indices.

• Enqueue: We calculate the index/pointer and insert. No loops. $O(1)$.
• Dequeue: We calculate the index/pointer and remove. No loops. $O(1)$.
• Note: Rust’s VecDeque might occasionally resize (grow), making enqueue Amortized $O(1)$, but this is standard for all dynamic arrays.

2. Queue using Stacks (Amortized $O(1)$)

This is the most common follow-up question in interviews.

Why is it Amortized $O(1)$?

• Enqueue: We simply push to s1. This is always $O(1)$.
• Dequeue (Worst Case): If s2 is empty, we must move all $N$ items from s1 to s2. This takes $O(N)$.
• Dequeue (Best Case): If s2 has items, we just pop one. This takes $O(1)$.

The Math (Amortized Analysis): Consider the lifecycle of a single element X:

1. Pushed onto s1 (Cost: 1)
2. Popped from s1 (Cost: 1)
3. Pushed onto s2 (Cost: 1)
4. Popped from s2 (Cost: 1)

Total operations for X over its entire life = 4 operations. Since 4 is a constant, the average cost per element is $O(1)$.