A queue is a fundamental data structure in computer science that follows the FIFO principle: First In, First Out. That means the first element that goes into the queue is also the first one to come out.

FIFO order shows up in many real-world systems:

Queues are also a frequent topic in coding interviews, especially in problems that involve ordered processing or level-by-level traversal.

This chapter covers:

A queue is a linear data structure that processes elements in the order they arrive, following the FIFO principle: First In, First Out.

A common analogy is people standing in line at a movie theater. The first person to join the line is the first to get a ticket. New arrivals join at the back, and the front of the line is where service happens.

A queue supports four standard operations: enqueue, dequeue, peek, and isEmpty.

1. Enqueue

This operation adds an element to the back of the queue. Starting with an empty queue, we enqueue 3 values one by one:

Enqueue(10):

Enqueue(20):

Enqueue(30):

2. Dequeue

This removes the front-most element from the queue.

For our example, after Dequeue(), we remove 10 since it was the first element that got added:

Dequeue():

3. Peek (or Front)

This lets you look at the front element without removing it.

Calling Peek() on our current example gives you 20, but the queue stays unchanged.

4. IsEmpty

The isEmpty operation checks whether the queue contains any elements. On our current queue it returns false; after dequeueing both 20 and 30 it would return true.

All four operations run in O(1) time, which is what makes queues efficient.

There are two common ways to implement a queue.

The most basic implementation uses an array.

If you use a plain array, removing the front element means shifting every remaining element one position to the left. That costs O(n) time, which is inefficient for large queues.

To avoid shifting, we use a circular array (or circular buffer).

The idea is to keep two indices, front and rear, that move forward as elements are enqueued and dequeued. When either index reaches the last slot of the array, it wraps back around to index 0 instead of running off the end.

The visualization below walks through a capacity-5 circular queue. Yellow marks front, orange marks rear. Empty slots are shown as null.

In the last frame, rear has wrapped from index 4 back to index 0 because slots 0 and 1 were freed by earlier dequeues. The queue still holds 30, 40, 50, 60 in FIFO order, even though the underlying array reads [60, null, 30, 40, 50] left to right.

This wraparound is what gives the circular array its name. Both enqueue and dequeue become O(1) because we never shift elements: we only move the two indices.

The arithmetic that makes this work is a single modulo:

Here's how we can implement this in code:

This circular movement ensures that we can reuse slots freed up by dequeue operations, preventing wasted space at the beginning of the array.

By wrapping around both front and rear using % capacity, we keep the queue compact and efficient, without needing to shift elements.

Another popular and efficient way to implement a queue is using a linked list.

A linked list grows and shrinks dynamically with no need to shift elements. Both enqueue and dequeue run in O(1) without the complexity of circular indexing.

We maintain two pointers:

In most coding interviews, and almost all real-world projects, you don't need to build a queue from scratch.

Because modern programming languages already provide efficient, well-tested, and optimized queue implementations in their standard libraries.

Java

Java provides a Queue interface, with popular implementations like LinkedList and ArrayDeque.

Python

Python doesn't have a built-in Queue class for general use in the core language (the queue module exists, but it's designed for thread-safe communication and is slower for single-threaded work). For algorithmic queues, the standard tool is collections.deque, which supports O(1) appends and pops at both ends.

C++

C++'s Standard Template Library provides std::queue, a container adapter built on top of std::deque by default.

C#

C# offers System.Collections.Generic.Queue<T>, a generic FIFO queue backed by a circular array.

Go

Go has no built-in queue type, but a slice with append and a slice-from-1 dequeue gives FIFO behavior. For long-running queues, a linked-list-based ring or container/list avoids the cost of repeatedly reslicing.

Rust

Rust's standard library provides VecDeque, a growable ring buffer that supports O(1) inserts and removes at both ends.

JavaScript

JavaScript has no built-in queue. Arrays work for small queues with push and shift, but shift is O(n) because it re-indexes the array. For large queues, use a custom linked-list implementation or a third-party deque.

TypeScript

TypeScript uses the same approach as JavaScript with explicit element types.

These libraries are optimized and ready to use, so unless you are explicitly asked to implement a queue from scratch, the standard library is the right starting point.

The plain FIFO queue covered so far is the simplest form. Three common variants exist, each designed for a different use case.

1. Simple Queue

This is the basic FIFO queue covered above.

However, when implemented using a simple array, it can lead to wasted space. After several dequeues, the front keeps moving forward, leaving unused slots at the beginning of the array.

To fix this, we use a smarter version, the circular queue.

2. Circular Queue

A circular queue eliminates the wasted-space problem by treating the array as circular.

Circular queues are especially useful in memory-constrained environments, like buffering systems or resource scheduling.

3. Deque (Double-Ended Queue)

A deque (pronounced "deck"), short for double-ended queue, is a generalization of the queue where insertion and removal are allowed at both ends. It supports four primary operations:

The four operations together let a deque behave as either a queue or a stack depending on which ends you use:

Internally, deques are typically backed by a doubly linked list or a circular array that supports cheap operations at both ends. In a circular-array implementation, the same wraparound trick we saw earlier applies, but now both front and rear can move in either direction.

The four operations run in O(1) in standard implementations like Java's ArrayDeque, Python's collections.deque, C++'s std::deque, and Rust's VecDeque.

Common use cases:

4. Priority Queue

A priority queue doesn't follow FIFO. Instead, each element carries a priority, and dequeue always removes the element with the highest priority (or the lowest, depending on configuration).

The two main operations:

How it works internally

A priority queue is almost always implemented with a binary heap, a complete binary tree stored in an array where every parent is greater than or equal to its children (max-heap) or less than or equal (min-heap). This shape gives the following guarantees:

Heaps are covered in detail in their own chapter; for now it's enough to know that the priority queue's speed comes from this underlying heap structure.

A classic real-world example is task scheduling. An operating system maintains a queue of tasks where each task has a priority level. High-priority tasks (like keyboard input or an interrupt handler) get to run before lower-priority background work, even if the background work was queued first.

Other common use cases:

This chapter focused on queues and their three close cousins: the circular queue, the deque, and the priority queue.