The Line at the Store Analogy
Picture a line at a grocery store:
- First person in line gets served first
- New people join at the back
- No cutting! You wait your turn
Queues work exactly like this.
The first item added is the first one removed. This is called FIFO: First In, First Out.
Queue Operations
The Core Four
ENQUEUE - Add item to back
Queue: [A, B]
enqueue(C)
Queue: [A, B, C] ← C joins the back
DEQUEUE - Remove and return front item
Queue: [A, B, C]
dequeue() → returns A
Queue: [B, C] ← A is gone, B is now front
FRONT/PEEK - Look at front item (without removing)
Queue: [A, B, C]
front() → returns A
Queue: [A, B, C] ← A still there
IS_EMPTY - Check if queue has items
Queue: []
isEmpty() → true
All O(1) Operations!
Every queue operation is constant time - no waiting in line for the computer!
Visual Walkthrough
Empty queue:
Front → [ ] ← Back
enqueue(1):
Front → [ 1 ] ← Back
enqueue(2):
Front → [ 1 | 2 ] ← Back
enqueue(3):
Front → [ 1 | 2 | 3 ] ← Back
dequeue() → 1:
Front → [ 2 | 3 ] ← Back
dequeue() → 2:
Front → [ 3 ] ← Back
peek() → 3 (queue unchanged)
Where Queues Are Used
1. Breadth-First Search (BFS)
Explore graph level by level:
Queue: [A] Process A, add neighbors B, C
Queue: [B, C] Process B, add neighbor D
Queue: [C, D] Process C
Queue: [D] Process D
Queue: [] Done!
FIFO ensures we visit nodes in order of distance.
2. Print Queue
Documents waiting to print:
Queue: [Doc1, Doc2, Doc3]
Printer takes Doc1 (first in line)
Queue: [Doc2, Doc3]
New document arrives:
Queue: [Doc2, Doc3, Doc4]
3. Task Scheduling
Web server handling requests:
Requests arrive: R1, R2, R3, R4
Queue: [R1, R2, R3, R4]
Server processes R1 first (arrived first)
Queue: [R2, R3, R4]
4. Message Queues
Microservices communication:
Service A sends messages to queue
Service B processes messages in order
Queue ensures messages aren't lost and order is preserved.
Queue Variations
Circular Queue
Fixed-size queue that wraps around:
Array: [_, _, C, D, E]
↑ ↑
back front
When back reaches end, it wraps to beginning.
Efficient use of fixed space!
Priority Queue
Items have priorities, highest priority served first:
Regular queue: serve in arrival order
Priority queue: serve by importance
Hospital ER: Critical patients before minor injuries,
regardless of arrival time.
Double-Ended Queue (Deque)
Add/remove from BOTH ends:
Regular queue: add back, remove front (typically)
Deque: add/remove from both ends
Useful for sliding window problems!
Classic Queue Problems
1. Implement Queue with Stacks
Problem: Build a queue using stacks.
Two stacks: inbox, outbox
enqueue(x): push to inbox
dequeue():
if outbox empty: move all from inbox to outbox
pop from outbox
Why it works:
Inbox: [3, 2, 1] (1 was added first)
Move to outbox: [1, 2, 3]
Pop outbox → 1 (the first one added!)
2. Sliding Window Maximum
Problem: Find maximum in each window of size k.
Array: [1, 3, -1, -3, 5, 3], k=3
Use deque to track potential maximums:
Window [1,3,-1]: max = 3
Window [3,-1,-3]: max = 3
Window [-1,-3,5]: max = 5
Window [-3,5,3]: max = 5
3. Number of Recent Calls
Problem: Count calls in the most recent time window.
Calls at: t1, t2, t3, t4
At time t3:
Queue: [t1, t2, t3]
Remove calls older than (t3 - window)
Queue: [t2, t3] (removed t1)
Count: 2
4. Rotting Oranges
Problem: How long for rot to spread to all oranges?
Grid with fresh (1) and rotten (2) oranges.
BFS from all rotten oranges:
Queue: [all initially rotten positions]
Each step: rot spreads to adjacent fresh oranges
Count minutes until no fresh remain.
Stack vs Queue
| Property | Stack | Queue |
|---|---|---|
| Order | LIFO | FIFO |
| Add | Top (push) | Back (enqueue) |
| Remove | Top (pop) | Front (dequeue) |
| Analogy | Stack of plates | Line at store |
| Traversal | DFS | BFS |
Implementation Options
Array-Based (Circular)
Queue in circular array:
[C, D, _, _, A, B]
↑ ↑
back front
Advantages: O(1) all operations, fixed memory
Challenge: Typically handle wrap-around
Linked List-Based
Queue with linked list:
front → [A] → [B] → [C] → null ← back
enqueue: add node at back
dequeue: remove node at front
Advantages: No size limit
Common Mistakes
1. Dequeue from Empty Queue
Usually check isEmpty() (or handle an empty case) before dequeue() or front().
2. Using Stack When Queue Needed
DFS uses stack, BFS uses queue. Mixing them up changes the traversal order!
3. Array Queue Without Circular Logic
Without circular logic, you'll waste space or need to shift elements.
FAQ
Q: When should I use a queue?
When you need to process items in the order they arrived - scheduling, BFS, streaming.
Q: Queue vs stack - how do I choose?
Need first item first? Queue (FIFO). Need last item first? Stack (LIFO).
Q: What's a blocking queue?
A queue that waits when empty (for producer-consumer patterns in multithreading).
Q: Why is BFS associated with queues?
BFS explores by distance from start. Queue's FIFO ensures we process nearer nodes before farther ones.
Summary
A queue is a FIFO data structure - first in, first out.
Key Takeaways:
- Enqueue, dequeue, front - all O(1)
- FIFO: First In, First Out
- Used in: BFS, scheduling, message passing
- Variations: circular, priority, deque
- Array (circular) or linked list implementation
- Essential for level-order processing
Queues maintain order - crucial for fair scheduling and BFS!
Related Concepts
Leave a Comment
Comments (0)
Be the first to comment on this concept.
Comments are approved automatically.