Queues, Circular Queues, Deques and Priority Queues

A queue is a linear abstract data type that accepts new items at one end and removes existing items at the other. The insertion end is the rear and the removal end is the front. Because the earliest inserted item is removed first, an ordinary queue follows first in, first out order, abbreviated FIFO.

Queues model waiting lines and streams of pending work. A print service handles earlier jobs before later ones, a server may hold incoming requests until workers are available and breadth-first search processes vertices in the order in which they are discovered. The queue abstraction expresses this ordering without tying the program to a particular array or linked representation.

Queue Operations and Invariants

The usual operations are:

• enqueue(x) inserts x at the rear.
• dequeue() removes and returns the item at the front.
• peek() or front() reads the front item without removing it.
• isEmpty() reports whether no items are stored.
• size() reports the number of stored items.

If A, B and C are enqueued in that order, three dequeues return A, then B, then C. Enqueue and dequeue should normally take O(1) time. Removing from an empty queue is underflow. Enqueuing into a full fixed-capacity representation is overflow. As with a stack, the API must define whether these conditions throw exceptions, return status values or trigger storage growth.

The logical invariant is that repeatedly dequeuing returns all currently stored elements in their insertion order. An implementation may arrange those values differently in memory, especially after a circular array wraps, but its public behavior must preserve FIFO order.

Why a Simple Array Needs Care

One elementary array design keeps the front item at index zero. Enqueue writes after the last item, but dequeue removes index zero and shifts every remaining item one position to the left. That shift touches a number of elements proportional to the queue size, so each dequeue takes O(n) time. A sequence of many removals can therefore take quadratic time.

Another design advances a front index instead of shifting. It provides constant-time removal, but a noncircular version may appear full when the rear reaches the last array position even though earlier positions have become free. Moving all elements back to the beginning merely postpones the same copying cost. A circular queue solves the problem by treating the end of the array as adjacent to its beginning.

Circular Array Queues

A circular queue stores values in a fixed array and wraps indices using modulo arithmetic. For capacity c, the position after index i is:

(i + 1) % c

Thus the successor of c - 1 is zero. A front index identifies the first logical item, while a rear-related index identifies either the last item or the next insertion position, depending on the selected convention. Physical order and logical order can differ: if front is near the end and the queue wraps, later logical items occupy low array indices.

There are several correct representation conventions. They must not be mixed.

Count-Based Convention

Maintain front, rear and count, where rear is the next insertion position. The queue is empty when count == 0 and full when count == capacity. Enqueue stores at rear, advances rear modulo capacity and increments count. Dequeue reads at front, advances front and decrements count.

This convention can use every array position and makes empty and full tests explicit. The extra count must be updated consistently. When count is zero, the numeric values of front and rear are implementation details; the count determines emptiness.

One-Unused-Slot Convention

Maintain front and rear, with rear again representing the next insertion position. Empty is indicated by front == rear. Full is indicated by (rear + 1) % capacity == front. One physical slot is always unused, so an array of length c holds at most c - 1 items. The unused position removes the ambiguity that would otherwise make equal indices mean both empty and full.

Full-Flag and Last-Element Conventions

A separate Boolean flag can distinguish the full and empty states when indices are equal, permitting use of all positions. Another convention lets rear identify the last occupied position rather than the next free one, which changes initialization and update formulas. Code and explanations must state the chosen meaning of each field because a formula copied from a different convention can silently corrupt the queue.

A dynamically growing circular queue allocates a larger array when full. It copies elements in logical order beginning with the old front, places them contiguously from index zero, sets the new front to zero and sets the next insertion index to the number of copied items. Copying physical indices from zero without accounting for wraparound changes FIFO order.

Linked Queues

A linked queue uses nodes and maintains references to both the first and last nodes. Enqueue creates a new node, connects the old tail to it and moves the tail reference. Dequeue saves the head value and advances the head reference. These operations take O(1) time because neither requires traversal.

The transition between empty and nonempty states needs special handling. When the first node is inserted, both head and tail refer to it. When the final node is removed, both references must become null. Leaving the tail pointing at the removed node creates a stale representation and may cause later insertions to connect incorrectly.

A linked queue grows as memory permits and wastes no reserved array capacity, but every element carries link and allocation overhead. An array queue usually has better locality. Either representation is correct when it preserves the same FIFO contract.

Deques

A deque, pronounced “deck,” is a double-ended queue. It supports insertion and removal at both front and rear:

• addFirst(x) and removeFirst() operate at the front.
• addLast(x) and removeLast() operate at the rear.
• peekFirst() and peekLast() inspect the two ends.

A deque can act as a queue by inserting at the rear and removing at the front. It can act as a stack by inserting and removing at the same end. Circular arrays and doubly linked lists are natural implementations because both can provide constant-time operations at either end.

An input-restricted deque permits insertion at only one end but removal at both. An output-restricted deque permits removal at only one end but insertion at both. These variants occur less often than the general deque but show that access rules, rather than storage alone, define the data type.

Deques support sliding-window algorithms. To find a maximum in every window, a monotonic deque stores candidate indices in decreasing value order. Expired indices leave from the front, while smaller candidates leave from the rear. Each index enters and leaves at most once, giving O(n) total time.

Priority Queues

An ordinary queue removes by arrival order. A priority queue removes according to priority. In a max-priority queue, the item with the greatest key is served first; in a min-priority queue, the smallest key is served first. Typical operations include insertion, reading the highest-priority item, removing it, changing a priority and testing emptiness.

Equal priorities need an explicit tie policy. A priority queue does not inherently preserve FIFO order among equal keys. Stable service can be obtained by attaching an increasing sequence number and comparing (priority, sequence) pairs. The priority decides first and arrival order breaks ties.

Different representations favor different operations. An unsorted array or list inserts in O(1) but may need O(n) time to find and remove the best item. A sorted sequence can expose the best item in O(1) but generally needs O(n) insertion. A balanced search tree supports major operations in O(log n) and can preserve ordered traversal. The most common general-purpose representation is a binary heap.

Binary Heaps as Priority Queues

A binary heap is a complete binary tree usually stored in an array. In a min-heap, every parent key is no greater than either child key. Consequently, the minimum appears at the root. In a max-heap, every parent is at least as large as its children, so the maximum appears at the root.

With zero-based indexing, a node at index i has children at 2i + 1 and 2i + 2, when those positions exist and a nonroot node has parent (i - 1) / 2 using integer division. Completeness keeps the tree height at O(log n) and avoids explicit child pointers.

Insertion places the new item at the next available array position, preserving completeness and then repeatedly exchanges it with its parent while the heap-order property is violated. This upward repair is called sift-up or percolate-up. It follows at most one root-to-leaf-height path and takes O(log n) worst-case time.

Removing the root saves the priority item, moves the last item to the root, reduces the heap size and repeatedly exchanges the replacement with its better-priority child. This sift-down process also takes O(log n). Reading the root takes O(1) because no movement is required. Building a heap bottom-up from an existing array takes O(n), a tighter bound than inserting all elements one at a time.

A heap guarantees only the parent-child priority relationship. Its array is not globally sorted and searching for an arbitrary value may still take O(n). Iterating the internal array does not produce complete priority order. Repeated root removal does, but it changes the heap and costs O(n log n) overall.

Queue Applications

Breadth-first search uses a FIFO queue. The start vertex is enqueued and marked discovered. Each dequeue processes the oldest discovered vertex and enqueues its undiscovered neighbors. In an unweighted graph, this layer-by-layer order finds paths with the fewest edges.

Operating systems and services use queues for scheduling, buffering and communication. A bounded buffer applies backpressure when producers run faster than consumers. A priority queue schedules work based on urgency, deadlines or estimated cost. Dijkstra’s algorithm uses a min-priority queue to select the unsettled vertex with the smallest tentative distance.

Queue correctness does not imply thread safety. Concurrent producers and consumers require synchronization or a data structure designed for concurrency. In Java, ArrayDeque is a useful non-thread-safe queue or deque for ordinary single-threaded work. PriorityQueue implements a heap-based priority queue, while concurrent and blocking queue classes provide different coordination guarantees.

The right structure follows from the required removal rule. Use an ordinary queue when arrival order controls service, a deque when both ends matter and a priority queue when a key controls service. Then choose the representation according to capacity, memory overhead, locality, resizing needs and concurrency requirements.