AntInLoop

Queue & Deque Data Structure Code Implementations

Production-ready Queue & Deque Data Structure data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.

Study Queue & Deque Data Structure Guide ยท Launch Visualizer

CPP Implementation

#include <iostream>
#include <stdexcept>
using namespace std;

template <typename T>
class Queue {
private:
    struct Node {
        T data;
        Node* next;
        
        Node(T value) : data(value), next(nullptr) {}
    };
    
    Node* front;
    Node* rear;
    int size;

public:
    Queue() : front(nullptr), rear(nullptr), size(0) {}
    
    ~Queue() {
        clear();
    }
    
    // Copy constructor
    Queue(const Queue& other) : front(nullptr), rear(nullptr), size(0) {
        Node* current = other.front;
        while (current) {
            enqueue(current->data);
            current = current->next;
        }
    }
    
    void enqueue(T value) {
        Node* newNode = new Node(value);
        if (rear) {
            rear->next = newNode;
        } else {
            front = newNode;
        }
        rear = newNode;
        size++;
    }
    
    T dequeue() {
        if (empty()) {
            throw runtime_error("Queue is empty");
        }
        T value = front->data;
        Node* temp = front;
        front = front->next;
        if (!front) {
            rear = nullptr;
        }
        delete temp;
        size--;
        return value;
    }
    
    T peek() const {
        if (empty()) {
            throw runtime_error("Queue is empty");
        }
        return front->data;
    }
    
    bool empty() const {
        return front == nullptr;
    }
    
    int length() const {
        return size;
    }
    
    void clear() {
        while (!empty()) {
            dequeue();
        }
    }
    
    bool contains(T value) const {
        Node* current = front;
        while (current) {
            if (current->data == value) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
    
    void display() const {
        if (empty()) {
            cout << "Queue: []" << endl;
            return;
        }
        
        cout << "Queue: front -> [";
        Node* current = front;
        while (current) {
            cout << current->data;
            if (current->next) cout << ", ";
            current = current->next;
        }
        cout << "] <- rear" << endl;
    }
};


/// circular

#include <iostream>
#include <stdexcept>
using namespace std;

template <typename T>
class ArrayQueue {
private:
    T* arr;
    int capacity;
    int frontIndex;
    int rearIndex;
    int size;
    
    void resize() {
        T* newArr = new T[capacity * 2];
        for (int i = 0; i < size; i++) {
            newArr[i] = arr[(frontIndex + i) % capacity];
        }
        delete[] arr;
        arr = newArr;
        frontIndex = 0;
        rearIndex = size - 1;
        capacity *= 2;
    }

public:
    ArrayQueue(int initialCapacity = 10) 
        : capacity(initialCapacity), frontIndex(0), rearIndex(-1), size(0) {
        arr = new T[capacity];
    }
    
    ~ArrayQueue() {
        delete[] arr;
    }
    
    void enqueue(T value) {
        if (size == capacity) {
            resize();
        }
        rearIndex = (rearIndex + 1) % capacity;
        arr[rearIndex] = value;
        size++;
    }
    
    T dequeue() {
        if (empty()) {
            throw runtime_error("Queue is empty");
        }
        T value = arr[frontIndex];
        frontIndex = (frontIndex + 1) % capacity;
        size--;
        return value;
    }
    
    T front() const {
        if (empty()) {
            throw runtime_error("Queue is empty");
        }
        return arr[frontIndex];
    }
    
    bool empty() const {
        return size == 0;
    }
    
    int length() const {
        return size;
    }
    
    void clear() {
        frontIndex = 0;
        rearIndex = -1;
        size = 0;
    }
};

JAVA Implementation

import java.util.NoSuchElementException;

public class Queue<T> {
    private class Node {
        T data;
        Node next;
        
        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }
    
    private Node front;
    private Node rear;
    private int size;
    
    public Queue() {
        front = null;
        rear = null;
        size = 0;
    }
    
    public void enqueue(T data) {
        Node newNode = new Node(data);
        if (rear != null) {
            rear.next = newNode;
        } else {
            front = newNode;
        }
        rear = newNode;
        size++;
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        T data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return data;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return front.data;
    }
    
    public boolean isEmpty() {
        return front == null;
    }
    
    public int size() {
        return size;
    }
    
    public void clear() {
        front = null;
        rear = null;
        size = 0;
    }
    
    public boolean contains(T data) {
        Node current = front;
        while (current != null) {
            if (current.data.equals(data)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
    
    @Override
    public String toString() {
        if (isEmpty()) {
            return "Queue: []";
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append("Queue: front -> [");
        Node current = front;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(", ");
            }
            current = current.next;
        }
        sb.append("] <- rear");
        return sb.toString();
    }
}


// using array

import java.util.Arrays;
import java.util.NoSuchElementException;

public class ArrayQueue<T> {
    private Object[] arr;
    private int front;
    private int rear;
    private int size;
    private int capacity;
    
    public ArrayQueue() {
        this(10);
    }
    
    public ArrayQueue(int initialCapacity) {
        this.capacity = initialCapacity;
        this.arr = new Object[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }
    
    public void enqueue(T data) {
        if (size == capacity) {
            resize();
        }
        rear = (rear + 1) % capacity;
        arr[rear] = data;
        size++;
    }
    
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        T data = (T) arr[front];
        arr[front] = null; // Help GC
        front = (front + 1) % capacity;
        size--;
        return data;
    }
    
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return (T) arr[front];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public int size() {
        return size;
    }
    
    public void clear() {
        Arrays.fill(arr, null);
        front = 0;
        rear = -1;
        size = 0;
    }
    
    private void resize() {
        Object[] newArr = new Object[capacity * 2];
        for (int i = 0; i < size; i++) {
            newArr[i] = arr[(front + i) % capacity];
        }
        arr = newArr;
        front = 0;
        rear = size - 1;
        capacity *= 2;
    }
}

JAVASCRIPT Implementation

class Queue {
    constructor() {
        this.items = [];
        this.frontIndex = 0;
    }
    
    // Add element to rear of queue
    enqueue(element) {
        this.items.push(element);
    }
    
    // Remove and return front element
    dequeue() {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        
        const element = this.items[this.frontIndex];
        this.frontIndex++;
        
        // Reset array when it gets too sparse
        if (this.frontIndex > this.items.length / 2) {
            this.items = this.items.slice(this.frontIndex);
            this.frontIndex = 0;
        }
        
        return element;
    }
    
    // Return front element without removing
    peek() {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.items[this.frontIndex];
    }
    
    // Check if queue is empty
    isEmpty() {
        return this.frontIndex >= this.items.length;
    }
    
    // Get queue size
    size() {
        return this.items.length - this.frontIndex;
    }
    
    // Clear the queue
    clear() {
        this.items = [];
        this.frontIndex = 0;
    }
    
    // Check if queue contains element
    contains(element) {
        return this.items.slice(this.frontIndex).includes(element);
    }
    
    // Convert to array (front to rear)
    toArray() {
        return this.items.slice(this.frontIndex);
    }
    
    // String representation
    toString() {
        if (this.isEmpty()) {
            return "Queue: []";
        }
        const elements = this.items.slice(this.frontIndex);
        return `Queue: front -> [${elements.join(', ')}] <- rear`;
    }
}

// linked list 

class LinkedQueue {
    constructor() {
        this.front = null;
        this.rear = null;
        this.count = 0;
    }
    
    enqueue(data) {
        const newNode = {
            data: data,
            next: null
        };
        
        if (this.rear) {
            this.rear.next = newNode;
        } else {
            this.front = newNode;
        }
        this.rear = newNode;
        this.count++;
    }
    
    dequeue() {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        
        const data = this.front.data;
        this.front = this.front.next;
        if (!this.front) {
            this.rear = null;
        }
        this.count--;
        return data;
    }
    
    peek() {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.front.data;
    }
    
    isEmpty() {
        return this.front === null;
    }
    
    size() {
        return this.count;
    }
    
    clear() {
        this.front = null;
        this.rear = null;
        this.count = 0;
    }
    
    contains(data) {
        let current = this.front;
        while (current) {
            if (current.data === data) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
    
    toArray() {
        const result = [];
        let current = this.front;
        while (current) {
            result.push(current.data);
            current = current.next;
        }
        return result;
    }
    
    toString() {
        if (this.isEmpty()) {
            return "Queue: []";
        }
        const elements = this.toArray();
        return `Queue: front -> [${elements.join(', ')}] <- rear`;
    }
}

PYTHON Implementation

## list 

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        """Add element to rear of queue"""
        self.items.append(item)
    
    def dequeue(self):
        """Remove and return front element"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items.popleft()
    
    def peek(self):
        """Return front element without removing"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items[0]
    
    def is_empty(self):
        """Check if queue is empty"""
        return len(self.items) == 0
    
    def size(self):
        """Get queue size"""
        return len(self.items)
    
    def clear(self):
        """Clear the queue"""
        self.items.clear()
    
    def contains(self, item):
        """Check if queue contains item"""
        return item in self.items
    
    def to_list(self):
        """Convert to list (front to rear)"""
        return list(self.items)
    
    def __len__(self):
        """Support len() function"""
        return len(self.items)
    
    def __bool__(self):
        """Support bool() function"""
        return not self.is_empty()
    
    def __str__(self):
        """String representation"""
        if self.is_empty():
            return "Queue: []"
        return f"Queue: front -> [{', '.join(map(str, self.items))}] <- rear"
    
    def __repr__(self):
        return f"Queue({list(self.items)})"
    
    def __iter__(self):
        """Make the queue iterable (front to rear)"""
        return iter(self.items)


## linked list

class LinkedQueue:
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    def __init__(self):
        self.front = None
        self.rear = None
        self.count = 0
    
    def enqueue(self, data):
        """Add element to rear of queue"""
        new_node = self.Node(data)
        if self.rear:
            self.rear.next = new_node
        else:
            self.front = new_node
        self.rear = new_node
        self.count += 1
    
    def dequeue(self):
        """Remove and return front element"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        data = self.front.data
        self.front = self.front.next
        if not self.front:
            self.rear = None
        self.count -= 1
        return data
    
    def peek(self):
        """Return front element without removing"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.front.data
    
    def is_empty(self):
        """Check if queue is empty"""
        return self.front is None
    
    def size(self):
        """Get queue size"""
        return self.count
    
    def clear(self):
        """Clear the queue"""
        self.front = None
        self.rear = None
        self.count = 0
    
    def contains(self, data):
        """Check if queue contains data"""
        current = self.front
        while current:
            if current.data == data:
                return True
            current = current.next
        return False
    
    def to_list(self):
        """Convert to list (front to rear)"""
        result = []
        current = self.front
        while current:
            result.append(current.data)
            current = current.next
        return result
    
    def __len__(self):
        return self.count
    
    def __bool__(self):
        return not self.is_empty()
    
    def __str__(self):
        if self.is_empty():
            return "Queue: []"
        elements = self.to_list()
        return f"Queue: front -> [{', '.join(map(str, elements))}] <- rear"
    
    def __iter__(self):
        """Make the queue iterable (front to rear)"""
        current = self.front
        while current:
            yield current.data
            current = current.next