Queue
A queue is a linear data structure that follows First-In-First-Out (FIFO) ordering: elements are added at the rear (enqueue) and removed from the front (dequeue), so the first element inserted is the first one removed. Queues model waiting…
Definition
A queue is a linear data structure that follows First-In-First-Out (FIFO) ordering: elements are added at the rear (enqueue) and removed from the front (dequeue), so the first element inserted is the first one removed. Queues model waiting lines and are fundamental to task scheduling, breadth-first traversal, and buffering between producers and consumers.
Overview
A queue enforces a strict order of processing: whatever enters first exits first, mirroring a physical line of people waiting. Core operations are enqueue (add to the rear), dequeue (remove from the front), peek/front (view the front element without removing it), and isEmpty. All are O(1) when implemented with a proper structure such as a doubly linked list or a circular buffer over an array; a naive array implementation that shifts elements after dequeue costs O(n) per removal. Variants extend the basic FIFO queue for specific needs. A circular queue reuses array space by wrapping indices around, avoiding the need to shift elements. A deque (double-ended queue) allows insertion and removal from both ends, generalizing both stacks and queues. A priority queue, typically implemented with a heap, dequeues elements by priority rather than arrival order, breaking strict FIFO in favor of importance-based ordering. Queues underpin breadth-first search (BFS) on trees and graphs, where nodes are processed level by level. In systems design, message queues (Kafka, RabbitMQ, SQS) apply the same FIFO principle at scale to decouple producers and consumers, buffer bursts of traffic, and enable asynchronous processing between services. Operating systems use queues for process scheduling (ready queue) and I/O request buffering, and print spoolers, call centers, and rate limiters all model real-world queuing behavior directly. Understanding queues is also foundational for reasoning about concurrency: bounded queues with blocking behavior are a common pattern for coordinating producer and consumer threads safely.
Key Concepts
- First-In-First-Out (FIFO) ordering
- Core operations: enqueue, dequeue, peek, isEmpty, all O(1) when well-implemented
- Circular queue implementation avoids costly element shifting
- Deque variant supports insertion/removal from both ends
- Priority queue variant orders by importance instead of arrival time
- Backbone of breadth-first search traversal
- Scales to distributed message queues (Kafka, RabbitMQ, SQS)