Here is the simple Queue Implementation(Array and Linked List):
There are two ways to implement a queue:
Using Array:
Array implementation of the queue is static and limited by size. However, it works faster than linked lists because the array memory is continuous and cache-friendly for the CPU. So, use the array-based implementation for the fixed amount of data.
‣ Representation of queue using Array
E.g.) Here is the representation of a Linear Queue with a capacity of 11. There are 10 elements inserted into the queue. So the Rear is at the index of 10 while the Front is at the index of 0.
Implementation of Queue using Array
public class ArrayQueue {
private int[] array;
private int front; // Index of the front element
private int rear; // Index of the rear element
private int size; // Current number of elements in the queue
private int capacity; // Maximum capacity of the queue
// Constructor to initialize the queue with a given capacity
public ArrayQueue(int capacity) {
this.capacity = capacity;
array = new int[capacity];
front = rear = -1; // Initialize front and rear to -1 to indicate an empty queue
size = 0;
}
// Method to check if the queue is empty
public boolean isEmpty() {
return size == 0;
}
// Method to check if the queue is full
public boolean isFull() {
return size == capacity;
}
// Method to enqueue an element into the queue
public void enqueue(int element) {
if (isFull()) {
System.out.println("Queue is full. Cannot enqueue.");
return;
}
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % capacity; // Circular increment
}
array[rear] = element;
size++;
}
// Method to dequeue an element from the queue
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue.");
return -1;
}
int element = array[front];
if (front == rear) {
front = rear = -1; // Reset front and rear to -1 to indicate an empty queue
} else {
front = (front + 1) % capacity; // Circular increment
}
size--;
return element;
}
// Method to get the front element of the queue without removing it
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty. No element to peek.");
return -1;
}
return array[front];
}
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(5); // Create a queue with capacity 5
// Enqueue elements into the queue
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// Print the front element of the queue
System.out.println("Front element: " + queue.peek());
// Dequeue and print elements from the queue
System.out.println("Dequeued: " + queue.dequeue());
System.out.println("Dequeued: " + queue.dequeue());
System.out.println("Dequeued: " + queue.dequeue());
// Try dequeuing from an empty queue
System.out.println("Dequeued: " + queue.dequeue());
}
}Using Linked List:
The linked list implementation of the queue is dynamic in size and grows/shrinks based on dynamic data. But it can be slower than the array as it requires runtime allocation and deallocation. So, use the linked list implementation only for the dynamic nature of data.
Representation of queue using Link List
Implementation of Queue using Linked List:
public class LinkedListQueue {
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node front; // Reference to the front (head) of the queue
private Node rear; // Reference to the rear (tail) of the queue
// Constructor to initialize an empty queue
public LinkedListQueue() {
front = rear = null;
}
// Method to check if the queue is empty
public boolean isEmpty() {
return front == null;
}
// Method to enqueue an element into the queue
public void enqueue(int element) {
Node newNode = new Node(element);
if (isEmpty()) {
front = rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
}
// Method to dequeue an element from the queue
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue.");
return -1; // Return -1 to indicate an empty queue
}
int removedElement = front.data;
front = front.next;
if (front == null) {
rear = null; // Update rear to null if the queue becomes empty after dequeue
}
return removedElement;
}
// Method to get the front element of the queue without removing it
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty. No element to peek.");
return -1; // Return -1 to indicate an empty queue
}
return front.data;
}
public static void main(String[] args) {
LinkedListQueue queue = new LinkedListQueue();
// Enqueue elements into the queue
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// Print the front element of the queue
System.out.println("Front element: " + queue.peek());
// Dequeue and print elements from the queue
System.out.println("Dequeued: " + queue.dequeue());
System.out.println("Dequeued: " + queue.dequeue());
System.out.println("Dequeued: " + queue.dequeue());
// Try dequeuing from an empty queue
System.out.println("Dequeued: " + queue.dequeue());
}
}
