Video Explanations:Queue Data Structure | Illustrated Data Structures

Definition

A Queue is a linear data structure that follows the FIFO principle: First In, First Out.

Imagine a line at a ticket counter 🎟️: the first person(Sarah) to arrive is the first person to be served.

Elements are added at the rear using enqueue() and removed from the front using dequeue(), following FIFO order.

Queues can be implemented using arrays, linked lists, or a circular buffer.

Types of Queues

Type	Description
Simple Queue	FIFO with basic operations.
Circular Queue	Circular Queue Reuses freed space in a fixed-size array to use memory more efficiently.
Deque	Double-ended queue (insert/remove from both ends)
Priority Queue	Elements are dequeued based on priority (Sorted), not strictly FIFO order. Priority queues can be implemented using Heap.

Key Operations

Operation	Description
`enqueue(x)`	Add element `x` to the rear of the queue
`dequeue()`	Remove and return the front element of the queue
`size()`	Return the number of elements in the queue
`peek()` / `front()`	Return the element at the front without removing it
`rear()`	Return the last/rear element without removing it (if supported)
`contains(x)`	Check if element `x` exists in the queue (if supported)
`isEmpty()`	Check whether the queue contains no elements
`clear()`	Remove all elements from the queue

Example

initialize the queue using an array: queue = [2, 4, 6, 8]
enqueue(10)          : Front → [2, 4, 6, 8, 10] ← Rear  // Add new element
dequeue() → 2        : Front → [4, 6, 8, 10] ← Rear     // Remove first element
peek() → 4           : Front → [4, 6, 8, 10] ← Rear     // Return first element
size() → 4           : Front → [4, 6, 8, 10] ← Rear
isEmpty() → false    : Front → [4, 6, 8, 10] ← Rear
contains(8) → true   : Front → [4, 6, 8, 10] ← Rear
clear()              : Front → [] ← Rear
isEmpty() → true

Implementation

// Queue implementation using an array with a front pointer
class Queue {
  constructor() {
    this.items = [];
    this.frontIndex = 0;
  }

  enqueue(x) {
    this.items.push(x);
  }

  dequeue() {
    if (this.isEmpty()) return undefined;

    const value = this.items[this.frontIndex];
    this.frontIndex++;

    // Optional cleanup to avoid unused memory growing forever
    if (this.frontIndex > 50 && this.frontIndex * 2 > this.items.length) {
      this.items = this.items.slice(this.frontIndex);
      this.frontIndex = 0;
    }

    return value;
  }

  size() {
    return this.items.length - this.frontIndex;
  }

  peek() {
    if (this.isEmpty()) return undefined;
    return this.items[this.frontIndex];
  }

  rear() {
    if (this.isEmpty()) return undefined;
    return this.items[this.items.length - 1];
  }

  contains(x) {
    for (let i = this.frontIndex; i < this.items.length; i++) {
      if (this.items[i] === x) return true;
    }

    return false;
  }

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

  clear() {
    this.items = [];
    this.frontIndex = 0;
  }
}

from collections import deque
from typing import Deque, Generic, Optional, TypeVar

T = TypeVar("T")


class Queue(Generic[T]):
    def __init__(self) -> None:
        self.items: Deque[T] = deque()

    def enqueue(self, x: T) -> None:
        self.items.append(x)

    def dequeue(self) -> Optional[T]:
        if self.is_empty():
            return None
        return self.items.popleft()

    def size(self) -> int:
        return len(self.items)

    def peek(self) -> Optional[T]:
        if self.is_empty():
            return None
        return self.items[0]

    def rear(self) -> Optional[T]:
        if self.is_empty():
            return None
        return self.items[-1]

    def contains(self, x: T) -> bool:
        return x in self.items

    def is_empty(self) -> bool:
        return len(self.items) == 0

    def clear(self) -> None:
        self.items.clear()

import java.util.ArrayDeque;

public class Queue<T> {
    private final ArrayDeque<T> items;

    public Queue() {
        this.items = new ArrayDeque<>();
    }

    public void enqueue(T x) {
        items.addLast(x);
    }

    public T dequeue() {
        return items.pollFirst();
    }

    public int size() {
        return items.size();
    }

    public T peek() {
        return items.peekFirst();
    }

    public T rear() {
        return items.peekLast();
    }

    public boolean contains(T x) {
        return items.contains(x);
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

    public void clear() {
        items.clear();
    }
}

#include<deque>
#include<optional>

using namespace std;

template <typename T>
class Queue {
private:
    deque<T> items;

public:
    void enqueue(const T& x) {
        items.push_back(x);
    }

    optional<T> dequeue() {
        if (isEmpty()) return nullopt;

        T value = items.front();
        items.pop_front();
        return value;
    }

    int size() const {
        return static_cast<int>(items.size());
    }

    optional<T> peek() const {
        if (isEmpty()) return nullopt;
        return items.front();
    }

    optional<T> rear() const {
        if (isEmpty()) return nullopt;
        return items.back();
    }

    bool contains(const T& x) const {
        for (const T& item : items) {
            if (item == x) return true;
        }

        return false;
    }

    bool isEmpty() const {
        return items.empty();
    }

    void clear() {
        items.clear();
    }
};

#include<stdbool.h>
#include<stdlib.h>

typedef struct {
    int* items;
    int capacity;
    int front;
    int count;
} Queue;

Queue* queueCreate(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    if (queue == NULL) return NULL;

    queue->items = (int*)malloc(sizeof(int) * capacity);
    if (queue->items == NULL) {
        free(queue);
        return NULL;
    }

    queue->capacity = capacity;
    queue->front = 0;
    queue->count = 0;
    return queue;
}

bool queueIsEmpty(Queue* queue) {
    return queue->count == 0;
}

int queueSize(Queue* queue) {
    return queue->count;
}

bool queueEnqueue(Queue* queue, int x) {
    if (queue->count == queue->capacity) return false;

    int rearIndex = (queue->front + queue->count) % queue->capacity;
    queue->items[rearIndex] = x;
    queue->count++;
    return true;
}

bool queueDequeue(Queue* queue, int* result) {
    if (queueIsEmpty(queue)) return false;

    *result = queue->items[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->count--;
    return true;
}

bool queuePeek(Queue* queue, int* result) {
    if (queueIsEmpty(queue)) return false;

    *result = queue->items[queue->front];
    return true;
}

bool queueRear(Queue* queue, int* result) {
    if (queueIsEmpty(queue)) return false;

    int rearIndex = (queue->front + queue->count - 1) % queue->capacity;
    *result = queue->items[rearIndex];
    return true;
}

bool queueContains(Queue* queue, int x) {
    for (int i = 0; i < queue->count; i++) {
        int index = (queue->front + i) % queue->capacity;
        if (queue->items[index] == x) return true;
    }

    return false;
}

void queueClear(Queue* queue) {
    queue->front = 0;
    queue->count = 0;
}

void queueFree(Queue* queue) {
    free(queue->items);
    free(queue);
}

// Queue implementation using an array with a front pointer
class Queue<T> {
  private items: T[];
  private frontIndex: number;

  constructor() {
    this.items = [];
    this.frontIndex = 0;
  }

  enqueue(x: T): void {
    this.items.push(x);
  }

  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;

    const value = this.items[this.frontIndex];
    this.frontIndex++;

    // Optional cleanup to avoid unused memory growing forever
    if (this.frontIndex > 50 && this.frontIndex * 2 > this.items.length) {
      this.items = this.items.slice(this.frontIndex);
      this.frontIndex = 0;
    }

    return value;
  }

  size(): number {
    return this.items.length - this.frontIndex;
  }

  peek(): T | undefined {
    if (this.isEmpty()) return undefined;
    return this.items[this.frontIndex];
  }

  rear(): T | undefined {
    if (this.isEmpty()) return undefined;
    return this.items[this.items.length - 1];
  }

  contains(x: T): boolean {
    for (let i = this.frontIndex; i < this.items.length; i++) {
      if (this.items[i] === x) return true;
    }

    return false;
  }

  isEmpty(): boolean {
    return this.size() === 0;
  }

  clear(): void {
    this.items = [];
    this.frontIndex = 0;
  }
}

class Queue<T> {
    private val items = mutableListOf<T>()
    private var frontIndex = 0

    fun enqueue(x: T) {
        items.add(x)
    }

    fun dequeue(): T? {
        if (isEmpty()) return null

        val value = items[frontIndex]
        frontIndex++

        // Optional cleanup to avoid unused memory growing forever
        if (frontIndex > 50 && frontIndex * 2 > items.size) {
            val remainingItems = items.subList(frontIndex, items.size).toList()
            items.clear()
            items.addAll(remainingItems)
            frontIndex = 0
        }

        return value
    }

    fun size(): Int {
        return items.size - frontIndex
    }

    fun peek(): T? {
        if (isEmpty()) return null
        return items[frontIndex]
    }

    fun rear(): T? {
        if (isEmpty()) return null
        return items[items.size - 1]
    }

    fun contains(x: T): Boolean {
        for (i in frontIndex until items.size) {
            if (items[i] == x) return true
        }

        return false
    }

    fun isEmpty(): Boolean {
        return size() == 0
    }

    fun clear() {
        items.clear()
        frontIndex = 0
    }
}

final class Queue<T: Equatable> {
    private var items: [T] = []
    private var frontIndex: Int = 0

    func enqueue(_ x: T) {
        items.append(x)
    }

    func dequeue() -> T? {
        if isEmpty() { return nil }

        let value = items[frontIndex]
        frontIndex += 1

        // Optional cleanup to avoid unused memory growing forever
        if frontIndex > 50 && frontIndex * 2 > items.count {
            items.removeFirst(frontIndex)
            frontIndex = 0
        }

        return value
    }

    func size() -> Int {
        return items.count - frontIndex
    }

    func peek() -> T? {
        if isEmpty() { return nil }
        return items[frontIndex]
    }

    func rear() -> T? {
        if isEmpty() { return nil }
        return items.last
    }

    func contains(_ x: T) -> Bool {
        for i in frontIndex..<items.count {
            if items[i] == x { return true }
        }

        return false
    }

    func isEmpty() -> Bool {
        return size() == 0
    }

    func clear() {
        items.removeAll()
        frontIndex = 0
    }
}

using System;
using System.Collections.Generic;

public class Queue<T>
{
    private List<T> items;
    private int frontIndex;

    public Queue()
    {
        items = new List<T>();
        frontIndex = 0;
    }

    public void Enqueue(T x)
    {
        items.Add(x);
    }

    public T? Dequeue()
    {
        if (IsEmpty()) return default;

        T value = items[frontIndex];
        frontIndex++;

        // Optional cleanup to avoid unused memory growing forever
        if (frontIndex > 50 && frontIndex * 2 > items.Count)
        {
            items = items.GetRange(frontIndex, items.Count - frontIndex);
            frontIndex = 0;
        }

        return value;
    }

    public int Size()
    {
        return items.Count - frontIndex;
    }

    public T? Peek()
    {
        if (IsEmpty()) return default;
        return items[frontIndex];
    }

    public T? Rear()
    {
        if (IsEmpty()) return default;
        return items[items.Count - 1];
    }

    public bool Contains(T x)
    {
        EqualityComparer<T> comparer = EqualityComparer<T>.Default;

        for (int i = frontIndex; i < items.Count; i++)
        {
            if (comparer.Equals(items[i], x)) return true;
        }

        return false;
    }

    public bool IsEmpty()
    {
        return Size() == 0;
    }

    public void Clear()
    {
        items.Clear();
        frontIndex = 0;
    }
}

package queue

type Queue[T comparable] struct {
    items      []T
    frontIndex int
}

func NewQueue[T comparable]() *Queue[T] {
    return &Queue[T]{
        items:      []T{},
        frontIndex: 0,
    }
}

func (q *Queue[T]) Enqueue(x T) {
    q.items = append(q.items, x)
}

func (q *Queue[T]) Dequeue() (T, bool) {
    var zero T
    if q.IsEmpty() {
        return zero, false
    }

    value := q.items[q.frontIndex]
    q.frontIndex++

    // Optional cleanup to avoid unused memory growing forever
    if q.frontIndex > 50 && q.frontIndex*2 > len(q.items) {
        q.items = append([]T(nil), q.items[q.frontIndex:]...)
        q.frontIndex = 0
    }

    return value, true
}

func (q *Queue[T]) Size() int {
    return len(q.items) - q.frontIndex
}

func (q *Queue[T]) Peek() (T, bool) {
    var zero T
    if q.IsEmpty() {
        return zero, false
    }

    return q.items[q.frontIndex], true
}

func (q *Queue[T]) Rear() (T, bool) {
    var zero T
    if q.IsEmpty() {
        return zero, false
    }

    return q.items[len(q.items)-1], true
}

func (q *Queue[T]) Contains(x T) bool {
    for i := q.frontIndex; i < len(q.items); i++ {
        if q.items[i] == x {
            return true
        }
    }

    return false
}

func (q *Queue[T]) IsEmpty() bool {
    return q.Size() == 0
}

func (q *Queue[T]) Clear() {
    q.items = []T{}
    q.frontIndex = 0
}

Time & Space Complexity

Operation	Description	Time	Space
`enqueue(x)`	Add element to the end of the queue	O(1)	O(1)
`dequeue()`	Remove element from the front of the queue. `dequeue()` uses `shift()`, which is `O(n)` in JavaScript because it may re-index the remaining elements.	O(n)	O(1)
`size()`	Return the number of elements	O(1)	O(1)
`peek()`	Access the front element without removing it	O(1)	O(1)
`rear()`	Access the last (rear) element	O(1)	O(1)
`contains(x)`	Check whether a specific element exists	O(n)	O(1)
`isEmpty()`	Check if the queue is empty	O(1)	O(1)
`clear()`	Remove all elements from the queue O(1) or O(n), depending on implementation O(1)	O(1)	O(1)

Use Cases

Real-Life	Description
Ticket Counter Line	People are served in the order they arrive.
Call Center Support	Calls are answered in the order they are received.
Print Queue	Print jobs are processed in the FIFO order submitted.
Restaurant Orders	Orders are prepared and served sequentially.

Computer Science	Field	Description
Task Queues in Web Servers	Software Engineering	Stores tasks or requests waiting to be processed, often in arrival order.
Data Pipeline Stages	Data Science	Queues data batches between ETL stages so each stage can process data in order.
Request Rate Limiting	Security / API Design	Stores incoming requests before processing or throttling them to prevent overload.
Real-Time Stream Processing	AI / Analytics	Stores incoming events so they can be processed in time order.

Core Algorithmic	Description	How DSA is Used
Breadth-First Search (BFS)	Explore nodes level by level	Queue holds the next nodes to visit in order
Sliding Window Problems	Process subarrays of fixed size	Queue tracks elements within the current window
Task Scheduling	Execute tasks in order of arrival	Queue stores tasks waiting to be processed
Level Order Tree Traversal	Visit tree nodes by level	Queue stores nodes waiting to be visited