A Queue follows the FIFO (First In, First Out) principle, meaning the first element added is the first one removed.
1. LinkedList-based Queue
For a linked list-based queue, we maintain:
A front pointer (points to the first element)
A rear pointer (points to the last element)
Node Class
Each element in the queue is stored in a Node, which contains:
data: The value of the node
next: Pointer to the next node
class Node<E> {
E data;
Node<E> next;
Node(E data) {
this.data = data;
this.next = null;
}
}
Queue Class
public class CustomLinkedListQueue<E> {
private Node<E> front, rear;
private int size;
public CustomLinkedListQueue() {
this.front = this.rear = null;
this.size = 0;
}
}
Core Operations
Enqueue (Add an element to the rear)
public void enqueue(E data) {
Node<E> newNode = new Node<>(data);
if (rear == null) { // Empty queue case
front = rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
size++;
}
Dequeue (Remove and return the front element)
public E dequeue() {
if (isEmpty()) throw new RuntimeException("Queue is empty");
E data = front.data;
front = front.next;
if (front == null) rear = null; // Queue is now empty
size--;
return data;
}
Peek (View the front element without removing it)
public E peek() {
if (isEmpty()) throw new RuntimeException("Queue is empty");
return front.data;
}
Check if Queue is Empty
public boolean isEmpty() {
return front == null;
}
Get Queue Size
public int size() {
return size;
}
Print Queue
public void printQueue() {
Node<E> current = front;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
Complete Custom Queue Implementation
public class CustomLinkedListQueue<E> {
private Node<E> front, rear;
private int size;
public CustomLinkedListQueue() {
this.front = this.rear = null;
this.size = 0;
}
public void enqueue(E data) {
Node<E> newNode = new Node<>(data);
if (rear == null) {
front = rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
size++;
}
public E dequeue() {
if (isEmpty()) throw new RuntimeException("Queue is empty");
E data = front.data;
front = front.next;
if (front == null) rear = null;
size--;
return data;
}
public E peek() {
if (isEmpty()) throw new RuntimeException("Queue is empty");
return front.data;
}
public boolean isEmpty() {
return front == null;
}
public int size() {
return size;
}
public void printQueue() {
Node<E> current = front;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
CustomLinkedListQueue<Integer> queue = new CustomLinkedListQueue<>();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.printQueue(); // Output: 10 -> 20 -> 30 -> null
System.out.println("Front element: " + queue.peek()); // Output: 10
System.out.println("Dequeued: " + queue.dequeue()); // Output: 10
queue.printQueue(); // Output: 20 -> 30 -> null
System.out.println("Queue size: " + queue.size()); // Output: 2
}
}
Time Complexity Analysis
Operation
Complexity
Enqueue (enqueue)
O(1)
Dequeue (dequeue)
O(1)
Peek (peek)
O(1)
Is Empty (isEmpty)
O(1)
Get Size (size)
O(1)
Print Queue (printQueue)
O(n)
2. Array-based Queue
Queue Data Structure
For an array-based queue, we maintain:
A front pointer (points to the first element)
A rear pointer (points to the last element)
A size variable to track the number of elements
A fixed-size array to store elements
Queue Class Definition
public class CustomArrayQueue<E> {
private E[] queue;
private int front, rear, size, capacity;
@SuppressWarnings("unchecked")
public CustomArrayQueue(int capacity) {
this.capacity = capacity;
this.queue = (E[]) new Object[capacity];
this.front = this.size = 0;
this.rear = -1;
}
}
The queue is initialized with a fixed size.
front points to the first element.
rear tracks the last inserted element.
size keeps track of the number of elements.
Core Operations
Enqueue (Add an element at the rear)
public void enqueue(E data) {
if (size == capacity) throw new RuntimeException("Queue is full");
rear = (rear + 1) % capacity; // Circular increment
queue[rear] = data;
size++;
}
Dequeue (Remove and return the front element)
public E dequeue() {
if (isEmpty()) throw new RuntimeException("Queue is empty");
E data = queue[front];
queue[front] = null; // Help GC
front = (front + 1) % capacity; // Circular increment
size--;
return data;
}
Peek (View the front element without removing it)
public E peek() {
if (isEmpty()) throw new RuntimeException("Queue is empty");
return queue[front];
}
Check if Queue is Empty
public boolean isEmpty() {
return size == 0;
}
Check if Queue is Full
public boolean isFull() {
return size == capacity;
}
Get Queue Size
public int size() {
return size;
}
Print Queue
public void printQueue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
System.out.print("Queue: ");
for (int i = 0; i < size; i++) {
System.out.print(queue[(front + i) % capacity] + " ");
}
System.out.println();
}
Complete Custom Queue Implementation
public class CustomArrayQueue<E> {
private E[] queue;
private int front, rear, size, capacity;
@SuppressWarnings("unchecked")
public CustomArrayQueue(int capacity) {
this.capacity = capacity;
this.queue = (E[]) new Object[capacity];
this.front = this.size = 0;
this.rear = -1;
}
public void enqueue(E data) {
if (size == capacity) throw new RuntimeException("Queue is full");
rear = (rear + 1) % capacity; // Circular increment
queue[rear] = data;
size++;
}
public E dequeue() {
if (isEmpty()) throw new RuntimeException("Queue is empty");
E data = queue[front];
queue[front] = null; // Help GC
front = (front + 1) % capacity; // Circular increment
size--;
return data;
}
public E peek() {
if (isEmpty()) throw new RuntimeException("Queue is empty");
return queue[front];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public int size() {
return size;
}
public void printQueue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
System.out.print("Queue: ");
for (int i = 0; i < size; i++) {
System.out.print(queue[(front + i) % capacity] + " ");
}
System.out.println();
}
public static void main(String[] args) {
CustomArrayQueue<Integer> queue = new CustomArrayQueue<>(5);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.printQueue(); // Output: Queue: 10 20 30
System.out.println("Front element: " + queue.peek()); // Output: 10
System.out.println("Dequeued: " + queue.dequeue()); // Output: 10
queue.printQueue(); // Output: Queue: 20 30
System.out.println("Queue size: " + queue.size()); // Output: 2
}
}
