Queue Data Structure: Operations, Types, Code, Applications

What is Queue Data Structure?

A queue is a linear data structure that stores elements in an ordered sequence. It is an abstract data type, similar to a stack, but with a different rule: a queue serves the oldest element first, while a stack serves the newest first.

We insert data at one end of the queue, the rear, and remove data from the other end, the front.

Think of a queue at the cinema theatre counter. The person standing first in the queue gets the ticket and leaves the group, while a new person joins at the back end of the queue.

This is at the center of the working of a queue, known as the First In First Out (FIFO) principle.

New to data structures? Our beginner's guide to data structures and algorithms covers the basics, and the array guide helps too, because we build the queue on top of an array below.

Basic Operations of a Queue

We can perform the following operations on a queue:

The times assume the implementations further down this page. A queue needs two positions: the front pointer is used to peek at and dequeue an element, and the rear pointer marks where the next element is added. Adding to a full queue is called overflow, and removing from an empty queue is called underflow (Wikipedia: queue).

How does Queue work?

Here's how a queue's operations work when the queue is stored in an array:

• The front pointer points to the first element of the queue
• The rear pointer points to the last element
• In an empty queue, we set the values of front and rear to -1.

Enqueue Operation

• Check if the queue is full
• If the queue is empty, set front to 0
• Increase rear by 1
• Add the new element where rear is pointing.

Dequeue Operation

• Check if the queue is empty
• Return the element that is in the front position
• Increase front by 1. Rear stays the same.

We can keep dequeuing one element at a time. When the last element is removed, we reset both pointers to -1, which makes the queue empty again.

The diagram follows a queue with room for four elements. Here are the same steps in a table:

Time complexity of queue operations

How fast a queue is depends on how you build it. Enqueue and peek are cheap in every version. Dequeue is the one that changes: removing the first element of a plain array moves every other element, which makes it O(n).

MDN describes shift() as moving all the remaining values one place to the left, which is where the O(n) comes from. The Python documentation makes the same point for lists: pop(0) costs O(n) because the other elements have to move, while a collections.deque adds and removes at either end in O(1). Space is O(n) for n stored elements.

Implementation of Queue Data Structure

We can implement a queue in the following ways:

• Sequential allocation: the queue is stored in an array. With a fixed-size array the queue can hold only a limited number of elements. A dynamic array, such as a JavaScript array, grows as needed.
• Linked list allocation: each element is a node that points to the next one. A queue built on a linked list grows one node at a time, so it has no fixed limit other than the available memory.

Queue with front and rear pointers

This is the array version from the diagram above, written in JavaScript. Front and rear start at -1, the first enqueue moves front to 0, and every enqueue moves rear one place to the right.

class ArrayQueue {
  constructor(capacity) {
    this.data = new Array(capacity);
    this.front = -1;                     // -1 means the queue is empty
    this.rear = -1;
  }

  isEmpty() {
    return this.front === -1;
  }

  isFull() {
    return this.rear === this.data.length - 1;
  }

  enqueue(value) {
    if (this.isFull()) throw new Error('Queue overflow');
    if (this.isEmpty()) this.front = 0;  // first element: front moves from -1 to 0
    this.rear++;
    this.data[this.rear] = value;
  }

  dequeue() {
    if (this.isEmpty()) throw new Error('Queue underflow');
    const value = this.data[this.front];
    if (this.front === this.rear) {
      this.front = -1;                   // that was the last element: reset both pointers
      this.rear = -1;
    } else {
      this.front++;
    }
    return value;
  }

  peek() {
    if (this.isEmpty()) throw new Error('Queue is empty');
    return this.data[this.front];
  }
}

const q = new ArrayQueue(4);
console.log(q.front, q.rear);               // -1 -1   (empty queue)
q.enqueue('A');
console.log(q.front, q.rear);               // 0 0
q.enqueue('B');
console.log(q.front, q.rear);               // 0 1
q.enqueue('C');
q.enqueue('D');
console.log(q.front, q.rear, q.isFull());   // 0 3 true
console.log(q.dequeue());                   // A
console.log(q.front, q.rear, q.peek());     // 1 3 B
try {
  q.enqueue('E');                           // slot 0 is free, but rear is already at the last index
} catch (e) {
  console.log(e.message);                   // Queue overflow
}

The last lines show the weak spot. After one dequeue there is a free slot at index 0, but rear is already at the last index, so the queue reports overflow. A circular queue, described under the types of queue below, fixes this.

JavaScript program to implement a queue using an array

In everyday JavaScript you do not need fixed pointers. An array already grows, and push() adds at the rear while shift() removes from the front. Here is a queue class built on that:

class Queue {
  constructor() {
    this.items = [];
  }

  // add an element at the rear
  enqueue(element) {
    this.items.push(element);
  }

  // remove and return the element at the front
  dequeue() {
    if (this.isEmpty()) return undefined;
    return this.items.shift();
  }

  // view the front element without removing it
  peek() {
    return this.items[0];
  }

  // check if the queue is empty
  isEmpty() {
    return this.items.length === 0;
  }

  // the number of elements
  size() {
    return this.items.length;
  }

  // empty the queue
  clear() {
    this.items = [];
  }
}

const queue = new Queue();
queue.enqueue('Asha');
queue.enqueue('Ravi');
queue.enqueue('Meera');
console.log(queue.peek());      // Asha
console.log(queue.dequeue());   // Asha
console.log(queue.dequeue());   // Ravi
console.log(queue.size());      // 1
console.log(queue.isEmpty());   // false

This is the easiest version to read, but shift() moves every remaining element, so dequeue is O(n). For a long queue, keep a head index and never shift:

class FastQueue {
  constructor() {
    this.items = {};     // maps an index to its element
    this.head = 0;       // index of the front element
    this.tail = 0;       // index where the next element will be stored
  }

  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const element = this.items[this.head];
    delete this.items[this.head];        // no other element has to move
    this.head++;
    return element;
  }

  peek() {
    return this.items[this.head];
  }

  isEmpty() {
    return this.tail === this.head;
  }

  size() {
    return this.tail - this.head;
  }
}

const queue = new FastQueue();
queue.enqueue('Asha');
queue.enqueue('Ravi');
queue.enqueue('Meera');
console.log(queue.dequeue());   // Asha
console.log(queue.peek());      // Ravi
console.log(queue.size());      // 2

Queue using a linked list

With a linked list you keep two pointers: head at the front and tail at the rear. Enqueue links a new node after the tail and dequeue moves the head forward, so both are O(1) and nothing is ever shifted.

class QueueNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedQueue {
  constructor() {
    this.head = null;                     // front of the queue
    this.tail = null;                     // rear of the queue
    this.length = 0;
  }

  enqueue(value) {
    const node = new QueueNode(value);
    if (this.tail) this.tail.next = node; // link the old rear to the new node
    else this.head = node;                // the first element is both front and rear
    this.tail = node;
    this.length++;
  }

  dequeue() {
    if (!this.head) return undefined;     // underflow
    const value = this.head.value;
    this.head = this.head.next;
    if (!this.head) this.tail = null;     // the queue just became empty
    this.length--;
    return value;
  }

  peek() {
    return this.head ? this.head.value : undefined;
  }
}

const q = new LinkedQueue();
q.enqueue('A');
q.enqueue('B');
q.enqueue('C');
console.log(q.dequeue(), q.peek(), q.length);   // A B 2

Queue in Python and Java

Most languages ship a ready-made queue, so in real projects you rarely write your own.

In Java's Queue interface, offer, poll and peek return false or null instead of throwing an exception, while add, remove and element throw one. In JavaScript you build the queue from an array or a linked list, as above. A Python queue takes three lines:

from collections import deque

queue = deque()
queue.append('A')             # enqueue at the rear
queue.append('B')
queue.append('C')
print(queue.popleft())        # dequeue from the front: A
print(queue[0])               # peek at the front: B
print(len(queue), len(queue) == 0)   # size and isEmpty: 2 False

Types of Queue

Following are the different types of queues:

Simple Queue

It's the basic queue in which insertion happens at the rear end and deletion happens at the front end of the queue. Every example above is a simple queue.

Circular Queue

In a circular queue the last position is connected back to the first, so the array is treated as a circle. It follows the FIFO principle and is also known as a ring buffer. When the rear reaches the end of the array it wraps around to index 0 if that slot is free, so no space is wasted. The next position is always (index + 1) % capacity.

The class below keeps a count of the stored elements. That makes it easy to tell a full queue from an empty one, because when the front and rear positions meet, the queue could be either (Wikipedia: circular buffer).

class CircularQueue {
  constructor(capacity) {
    this.data = new Array(capacity);
    this.front = 0;                    // index of the oldest element
    this.count = 0;                    // how many elements are stored
  }

  isEmpty() {
    return this.count === 0;
  }

  isFull() {
    return this.count === this.data.length;
  }

  enqueue(value) {
    if (this.isFull()) throw new Error('Queue overflow');
    const rear = (this.front + this.count) % this.data.length;   // wraps past the end of the array
    this.data[rear] = value;
    this.count++;
  }

  dequeue() {
    if (this.isEmpty()) throw new Error('Queue underflow');
    const value = this.data[this.front];
    this.data[this.front] = undefined;
    this.front = (this.front + 1) % this.data.length;
    this.count--;
    return value;
  }
}

const q = new CircularQueue(4);
for (const letter of ['A', 'B', 'C', 'D']) q.enqueue(letter);
console.log(q.dequeue());     // A
q.enqueue('E');               // reuses the free slot at index 0
console.log(q.data);          // [ 'E', 'B', 'C', 'D' ]
console.log(q.isFull());      // true

Compare this with the front-and-rear version earlier: there, enqueuing E after one dequeue failed with overflow, and here it reuses the freed slot. Circular queues are used as ring buffers that hold data streams, and for round-robin CPU scheduling, where processes take turns in a repeating order.

Priority Queue

In a priority queue every element has a priority, and the element with the highest priority is removed first, not the oldest one. Whether “highest” means the smallest or the largest number is a convention: Java's PriorityQueue treats the lowest value as the highest priority, and so does Python's heapq. If two elements have the same priority, the order between them is not guaranteed unless you add a tie-breaker, such as an arrival counter.

A binary heap is the usual implementation. Inserting an element and removing the top one are both O(log n), and reading the top element is O(1) (Wikipedia: priority queue).

import heapq

tasks = []
heapq.heappush(tasks, (2, 'write report'))
heapq.heappush(tasks, (1, 'fix login bug'))
heapq.heappush(tasks, (3, 'update docs'))

while tasks:
    priority, task = heapq.heappop(tasks)   # the smallest number comes out first
    print(priority, task)

# Output:
# 1 fix login bug
# 2 write report
# 3 update docs

A few primary use cases for a priority queue are Dijkstra's shortest path algorithm, Prim's algorithm and Huffman coding for data compression. Routers also use priority queues to send high-priority traffic first.

Double-ended Queue

As the name suggests, a double-ended queue (deque, pronounced “deck”) allows both insertion and deletion at both ends. In other words, we can add elements at the rear and the front, and remove them from either end.

A deque generalizes both structures: used at one end only it behaves like a stack, and used at opposite ends it behaves like a queue. There are also two restricted forms. An input-restricted deque allows insertion at one end only, and an output-restricted deque allows removal at one end only.

from collections import deque

d = deque()
d.append('B')           # add at the rear
d.appendleft('A')       # add at the front
d.append('C')
print(d)                # deque(['A', 'B', 'C'])
print(d.popleft())      # A  (remove from the front)
print(d.pop())          # C  (remove from the rear)

A well-known use of a deque is work stealing: each processor takes tasks from one end of its own deque, and other processors steal tasks from the opposite end. A deque also gives a linear-time solution to the sliding-window maximum problem (Wikipedia: double-ended queue).

Types of queue compared

Difference between Stack and Queue

Despite both being linear data structures and abstract data types, a stack and a queue have major differences. Let's have a look:

The stack data structure guide covers the other side in the same way. In graph search the choice is exactly this one: keep the next nodes in a queue and you get breadth-first search, keep them in a stack and you get depth-first search (see the graph data structure guide).

Applications of Queue Data Structure

A queue keeps elements in the order they arrived, so it has many applications wherever work must be served first come, first served, or where a fast producer feeds a slow consumer. This is the short version. Our guide to the applications of queue explains each one with a worked example.

Classic queue interview problems

Most queue questions are variations of a few ideas: