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