Queues
A queue is a fundamental data structure that models real-world waiting lines. Just like people waiting in line at a coffee shop — the first person to arrive is the first to be served. This simple principle makes queues essential for scheduling, processing tasks in order, and traversing data structures.
What Is a Queue?#
A queue is a linear data structure that follows the FIFO (First In, First Out) principle. The first element added is the first one to be removed.
Real-World Analogies#
- Waiting line: First person in line is served first
- Printer queue: Documents print in the order they were sent
- Customer service: Calls are answered in the order received
- Traffic: Cars pass through a tunnel in arrival order
Key Characteristics#
| Property | Description |
|---|---|
| FIFO Order | First In, First Out — oldest element is accessed first |
| Two Access Points | Elements added at rear, removed from front |
| Dynamic Size | Can grow and shrink as elements are enqueued and dequeued |
| Sequential Access | Cannot access middle elements directly |
| Abstract Data Type | Can be implemented using arrays, linked lists, or circular buffers |
Queue Operations#
Queue operations work at both ends — adding at the rear and removing from the front.
| Operation | Time Complexity | Description |
|---|---|---|
| enqueue(item) | O(1) | Add element to the rear |
| dequeue() | O(1)* | Remove and return front element |
| front() / peek() | O(1) | Return front element without removing |
| rear() / back() | O(1) | Return rear element without removing |
| isEmpty() | O(1) | Check if queue is empty |
| size() | O(1) | Return number of elements |
* dequeue is O(1) when backed by a linked list or index-based approach; O(n) when using a plain array (shift/pop(0))
Visualizing Enqueue and Dequeue#
Queue Operations
Basic queue operations in Python and JavaScript
Queue Implementation#
Using a plain array with shift() (JavaScript) or list.pop(0) (Python) gives O(n) dequeue — every element must shift one position forward after each removal. A proper queue implementation avoids this by using a structure that supports O(1) removal from the front. The examples below use Python's deque (a doubly-linked list internally) and a JavaScript object with front/rear index pointers, both achieving O(1) for all operations.
Queue with O(1) Operations
Implement a queue using Python's deque or a JavaScript object with index tracking to achieve O(1) enqueue and dequeue
Types of Queues#
Different queue variants serve different purposes.
Simple Queue#
The basic queue described throughout this page — elements are enqueued at the rear and dequeued from the front. Suitable for most FIFO use cases where the queue size is not fixed.
Circular Queue#
A fixed-capacity queue where the rear index wraps around to index 0 when it reaches the end of the underlying array. This reuses freed slots from previous dequeues, eliminating wasted space without allocating new memory.
Priority Queue#
Each element has an associated priority, and the highest-priority element is dequeued first regardless of insertion order. Typically implemented with a heap, which gives O(log n) insert and remove. Used in graph algorithms such as Dijkstra's shortest path and Prim's minimum spanning tree.
Double-Ended Queue (Deque)#
Elements can be added or removed from both the front and the rear in O(1). This makes a deque a superset of both queues and stacks. It is commonly used for sliding-window problems where elements are added at one end and evicted from the other.
| Queue Type | Use Case | Complexity |
|---|---|---|
| Simple Queue | Task scheduling, BFS | O(1) enqueue/dequeue |
| Circular Queue | Fixed buffer, streaming | O(1), no wasted space |
| Priority Queue | Job scheduling, Dijkstra's | O(log n) insert/remove |
| Deque | Sliding window, palindrome | O(1) both ends |
Common Applications#
Queues are essential in many real-world systems and algorithms.
1. Breadth-First Search (BFS)#
BFS uses a queue to explore nodes level by level in graphs and trees.
2. Task Scheduling#
Operating systems maintain a ready queue of processes waiting for CPU time. Each process waits its turn, and the scheduler dequeues the next one to run. In round-robin scheduling, a process is re-enqueued at the rear after consuming its time slice, ensuring every process gets a fair share of the CPU.
3. Message Queues#
Distributed systems use message queues (such as RabbitMQ or Apache Kafka) to decouple producers from consumers. A producer enqueues messages; one or more consumers dequeue and process them independently and at their own pace. This prevents data loss when consumers are temporarily slower than producers and makes systems more resilient to traffic spikes.
4. Print Spooling#
When multiple users send documents to a shared printer, the jobs are placed in a queue. The printer dequeues and processes one job at a time in the order they were submitted, ensuring fair and predictable delivery without conflicts.
Classic Queue Algorithms#
BFS Level Order Traversal#
Traverse a tree level by level using a queue. The key insight is that a queue's FIFO order naturally processes all nodes at one depth before any nodes at the next depth. When a node is dequeued, its children are enqueued — so they will be processed only after all current-level nodes are done. The space complexity is O(w), where w is the maximum number of nodes at any single level; in the worst case (a complete binary tree), this equals O(n).
BFS Level Order Traversal
Visit all nodes in a tree level by level using a queue
Number of Recent Calls#
A practical sliding-window problem: given a stream of timestamps, count how many occurred within the last 3000 milliseconds. Each new timestamp is enqueued, and any timestamps that fall outside the window are discarded from the front. Because timestamps always arrive in increasing order, the queue stays sorted and we only ever remove from the front — making the queue a natural fit. The space complexity is O(w), where w is the maximum number of requests that can fall within the 3000ms window at any one time.
Recent Counter
Count how many requests occurred in the last 3000 milliseconds
Queue vs Stack#
| Aspect | Queue | Stack |
|---|---|---|
| Order | FIFO (First In, First Out) | LIFO (Last In, First Out) |
| Add operation | Enqueue at rear | Push at top |
| Remove operation | Dequeue from front | Pop from top |
| Access points | Two ends (front & rear) | One end (top only) |
| Use case | BFS, scheduling, buffering | DFS, undo, parsing |
| Real-world analogy | Line at a store | Stack of plates |
When to Use Queues#
| Scenario | Example |
|---|---|
| Level-by-level processing | BFS traversal, level order |
| First-come-first-served | Task scheduling, print jobs |
| Buffering | I/O buffers, streaming data |
| Asynchronous processing | Message queues, event handling |
| Sliding window problems | Moving average, rate limiting |
| Simulation | Customer service, traffic flow |
When to Consider Alternatives#
| Scenario | Better Alternative |
|---|---|
| Need LIFO order | Stack |
| Need priority-based ordering | Priority Queue / Heap |
| Need access to both ends | Deque |
| Need random access | Array |
| Need fast search | Hash Set / Hash Map |
Reviewing AI-Generated Code#
AI tools frequently generate queue code that is functionally correct but has hidden performance problems. The most common pitfall is using array.shift() in JavaScript or list.pop(0) in Python for dequeue — both operations run in O(n) because every remaining element must be shifted forward in memory. This looks harmless in small examples but silently degrades the algorithm to O(n²) for large inputs.
Another common mistake specific to level-order BFS is failing to snapshot the queue size before processing a level, causing all nodes to be lumped into a single level instead of being grouped correctly.
The table below summarizes what to check when reviewing AI-generated queue code:
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Dequeue efficiency | Is removal O(1)? | Using array.shift() in JavaScript (O(n)) |
| Empty queue | Check before dequeue | Calling dequeue on empty queue |
| BFS traversal | Processing order | Using stack instead of queue (becomes DFS) |
| Level tracking | Grouping by level | Not tracking level boundaries correctly |
| Queue vs Stack | FIFO vs LIFO | Confusing push/pop with enqueue/dequeue |
Spotting AI Queue Bugs
Common errors in AI-generated queue solutions
Summary#
| Concept | Key Takeaway |
|---|---|
| FIFO Principle | First In, First Out — oldest element accessed first |
| Core Operations | enqueue(), dequeue(), front() — aim for O(1) |
| Implementation | Use deque (Python) or custom class (JavaScript) for efficiency |
| Queue Types | Simple, Circular, Priority, Deque — each for different needs |
| Key Applications | BFS traversal, task scheduling, message queues |
| vs Stack | Queue for FIFO ordering, Stack for LIFO ordering |
The queue is a simple but powerful structure. Its FIFO property makes it ideal for processing things in order, traversing graphs level by level, and building fair scheduling systems. Understanding when to use a queue versus a stack — and recognizing performance pitfalls in common implementations — are fundamental skills in algorithm design.