🔁Data Structures Unit 3 Review

A queue is a collection where items are inserted at one end (the rear) and removed from the other end (the front). This makes it a First-In-First-Out (FIFO) structure: whatever goes in first comes out first, like a line at a grocery store.

The core operations of the Queue ADT are:

enqueue(element) — adds an element to the rear of the queue
dequeue() — removes and returns the element at the front of the queue
front() (sometimes called peek) — returns the front element without removing it
isEmpty() — returns true if the queue has no elements
size() — returns the number of elements currently in the queue

All five of these operations run in $O(1)$ time, which is what makes queues so practical for high-throughput processing.

Under the hood, queues are typically implemented with either a linked list or a circular array. A standard (non-circular) array implementation can cause problems: every dequeue shifts elements or wastes space at the front. A circular array solves this by wrapping the front and rear indices around using modular arithmetic.

Queue abstract data type, Queue Data Structure - Basics Behind

FIFO Principle

The FIFO principle is what distinguishes a queue from a stack. In a queue, the element that has been waiting the longest is always the next one served. In a stack, the most recently added element comes out first (LIFO).

Queue (FIFO): First element in is the first element out — like a line of people.

Stack (LIFO): Last element in is the first element out — like a stack of plates.

FIFO is the right model whenever fairness or ordering matters. Think of a ticket counter: the person who arrived first should be helped first. Any system that needs to preserve arrival order will use a queue.

Applications of Queues

Queues show up across many areas of computing. Here are the most important ones to know:

Task scheduling — Operating systems use queues to manage processes waiting for CPU time. A print spooler, for example, prints documents in the order they were submitted.
Breadth-First Search (BFS) — BFS explores a graph level by level. It uses a queue to track which nodes to visit next: enqueue all neighbors of the current node, then dequeue the next node to process. This guarantees you visit nodes in order of their distance from the start.
Message passing — In distributed systems, message queues (like RabbitMQ or Kafka) let components communicate asynchronously. The sender enqueues messages, and the receiver dequeues them in order.
Event handling — GUI frameworks maintain an event queue for user actions (key presses, mouse clicks). Events are processed in the order they occur, so the interface responds predictably.
Buffering — Queues act as buffers when a producer generates data faster than a consumer can process it. Streaming video, for instance, buffers frames in a queue so playback stays smooth.

Note on cache management: some guides list cache eviction as a queue application. While a simple FIFO cache does use a queue, most real caches (like LRU caches) use more complex structures. For this course, focus on the other applications above.

Time Complexity of Queue Operations

Every standard queue operation runs in $O(1)$ time, regardless of how many elements are in the queue. Here's why each one is constant time:

Operation	Time	How It Works
enqueue	$O(1)$	Appends to the rear. In a linked list, update the tail pointer. In a circular array, place at the rear index and increment.
dequeue	$O(1)$	Removes from the front. In a linked list, update the head pointer. In a circular array, increment the front index.
front	$O(1)$	Access the element at the front pointer/index without modifying anything.
isEmpty	$O(1)$	Check whether the size counter equals zero (or whether front and rear indices indicate an empty state).
size	$O(1)$	Return a maintained counter that gets incremented on enqueue and decremented on dequeue.

The key detail: these $O(1)$ guarantees depend on the implementation. A linked list gives $O(1)$ naturally. A circular array gives $O(1)$ amortized (with occasional resizing if the array fills up). A naive array where you shift elements on every dequeue would be $O(n)$ , which is why circular arrays are preferred.

🔁Data Structures Unit 3 Review