A queue is a First In, First Out (FIFO) data structure. The first thing we put in is the first thing we take out. Think of a line at a coffee shop — first person in line gets served first.
In simple language, a queue is the opposite of a stack. Instead of taking from the top (last in), we take from the front (first in).
Queue Operations
All O(1) time:
- enqueue(item) — add to the back
- dequeue() — remove from the front
- front() / peek() — look at the front without removing
- isEmpty() — check if the queue is empty
Using Queues in Each Language
// JavaScript -- no built-in queue, use array (or linked list for O(1))
const queue = [];
queue.push(10); // enqueue to back
queue.push(20);
queue.push(30);
queue.shift(); // 10 -- dequeue from front (O(n) with arrays!)
queue[0]; // 20 -- peek at front
// For O(1) dequeue, use a Map or linked list implementation
// In interviews, array is usually fine# Python -- use collections.deque (O(1) both ends)
from collections import deque
queue = deque()
queue.append(10) # enqueue to back
queue.append(20)
queue.append(30)
queue.popleft() # 10 -- dequeue from front, O(1)!
queue[0] # 20 -- peek at front// Java -- use LinkedList or ArrayDeque as Queue
Queue<Integer> queue = new LinkedList<>();
queue.offer(10); // enqueue to back
queue.offer(20);
queue.offer(30);
queue.poll(); // 10 -- dequeue from front
queue.peek(); // 20 -- peek at frontJavaScript gotcha: Array.shift() is O(n) because it has to re-index everything. For performance-critical code, we’d use a linked list. But in interviews, the array approach is usually acceptable.
Queues and BFS
Queues are the backbone of Breadth-First Search (BFS). BFS explores all neighbors at the current depth before moving deeper. The queue ensures we process nodes level by level.
// BFS using a queue -- level order traversal
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
while (queue.length) {
const node = queue.shift(); // process front of queue
console.log(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor); // add neighbors to back
}
}
}
}# BFS using a queue -- level order traversal
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft() # process front of queue
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor) # add neighbors to back// BFS using a queue -- level order traversal
static void bfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll(); // process front of queue
System.out.println(node);
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor); // add neighbors to back
}
}
}
}We’ll dive deep into BFS in the graphs topic. For now, just remember: BFS = queue, DFS = stack (or recursion).
Deque — Double-Ended Queue
A deque (pronounced “deck”) allows adding and removing from both ends in O(1). It’s like a queue and a stack combined.
removeFirst <-->
removeLast
// JavaScript doesn't have a native deque
// Use an array (shift is O(n)) or implement with doubly linked list
const deque = [];
deque.push(10); // addLast
deque.unshift(5); // addFirst (O(n) with array)
deque.pop(); // removeLast
deque.shift(); // removeFirst (O(n) with array)# Python deque -- O(1) on both ends
from collections import deque
dq = deque()
dq.append(10) # addLast
dq.appendleft(5) # addFirst
dq.pop() # removeLast -> 10
dq.popleft() # removeFirst -> 5// Java ArrayDeque -- O(1) on both ends
Deque<Integer> deque = new ArrayDeque<>();
deque.addLast(10); // addLast
deque.addFirst(5); // addFirst
deque.removeLast(); // removeLast -> 10
deque.removeFirst(); // removeFirst -> 5Classic Problem: Sliding Window Maximum
Given an array and a window size k, find the maximum value in each window as it slides from left to right. This is THE classic deque problem.
Brute force: for each window, scan all k elements. That’s O(n * k).
With a deque: maintain a monotonically decreasing deque of indices. The front always holds the index of the current window’s maximum. We get O(n).
// Sliding window maximum -- O(n) using deque
function maxSlidingWindow(nums, k) {
const result = [];
const deque = []; // stores indices, values decrease front to back
for (let i = 0; i < nums.length; i++) {
// remove indices outside the window
if (deque.length && deque[0] <= i - k) {
deque.shift();
}
// remove smaller elements from back (they'll never be max)
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
deque.push(i);
// window is fully formed starting at index k-1
if (i >= k - 1) {
result.push(nums[deque[0]]); // front is the max
}
}
return result;
}
// [1, 3, -1, -3, 5, 3, 6, 7], k=3 -> [3, 3, 5, 5, 6, 7]# Sliding window maximum -- O(n) using deque
from collections import deque
def max_sliding_window(nums, k):
result = []
dq = deque() # stores indices, values decrease front to back
for i in range(len(nums)):
# remove indices outside the window
if dq and dq[0] <= i - k:
dq.popleft()
# remove smaller elements from back
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
dq.append(i)
# window is fully formed starting at index k-1
if i >= k - 1:
result.append(nums[dq[0]]) # front is the max
return result
# [1, 3, -1, -3, 5, 3, 6, 7], k=3 -> [3, 3, 5, 5, 6, 7]// Sliding window maximum -- O(n) using deque
static int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
int idx = 0;
for (int i = 0; i < nums.length; i++) {
// remove indices outside the window
if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// remove smaller elements from back
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.addLast(i);
if (i >= k - 1) {
result[idx++] = nums[deque.peekFirst()]; // front is max
}
}
return result;
}
// [1, 3, -1, -3, 5, 3, 6, 7], k=3 -> [3, 3, 5, 5, 6, 7]This combines a sliding window with a monotonic deque. Each element is added and removed from the deque at most once, so the total time is O(n).
Queue vs Stack vs Deque
| Structure | Insert | Remove | Use Case |
|---|---|---|---|
| Stack | Top - O(1) | Top - O(1) | DFS, undo, matching pairs |
| Queue | Back - O(1) | Front - O(1) | BFS, scheduling, buffering |
| Deque | Both ends - O(1) | Both ends - O(1) | Sliding window, palindrome check |
When to Think Queue or Deque
- Processing in order: Tasks, print jobs, message queues — anything “first come, first served”
- Level-by-level traversal: BFS on trees and graphs
- Sliding window maximum/minimum: Deque with monotonic ordering
- Recent history with expiration: Remove old items from front, add new to back
The big takeaway: if the problem says “process in order” or “level by level”, we want a queue. If we need efficient access to both ends, we want a deque.