Java Program to Implement the queue data structure

Introduction

A queue is a fundamental data structure that operates on a First-In-First-Out (FIFO) principle, where elements added first are accessed first. This structure is used extensively in various programming applications, such as data buffering, breadth-first search in graphs, and handling of interrupts in operating systems.

In this article, you will learn how to implement a queue in Java. Discover the various methods involved in manipulating a queue, such as enqueue (adding elements), dequeue (removing elements), and peeking (viewing the front element without removing it). Each of these operations will be illustrated with Java code examples for clear understanding.

Implementing Queue Using Array

Basic Structure

1. Define the necessary attributes for a queue class, such as the array itself, the maximum size of the queue, front and rear pointers, and the size of the current queue.

   java Copy

   public class ArrayQueue {
       private int arr[];
       private int front;
       private int rear;
       private int capacity;
       private int count;
   
       ArrayQueue(int size) {
           arr = new int[size];
           capacity = size;
           front = 0;
           rear = -1;
           count = 0;
       }
   }
   

   This code initializes a new queue with a specific size. The front and rear are indexes to manage where elements are added or removed.

Enqueue Operation

1. Add elements to the rear of the queue. Ensure that the queue is not full before adding a new element.

   java Copy

   public void enqueue(int item) {
       if (isFull()) {
           System.out.println("Queue is full");
           return;
       }
       rear = (rear + 1) % capacity;
       arr[rear] = item;
       count++;
   }
   
   public boolean isFull() {
       return (count == capacity);
   }
   

   In this snippet, enqueue adds an element at the position just after rear and wraps around using modulo arithmetic if the end of the array is reached. The capacity check prevents overflow.

Dequeue Operation

1. Remove and return the front element of the queue. Ensure that the queue is not empty before performing this operation.

   java Copy

   public int dequeue() {
       if (isEmpty()) {
           System.out.println("Queue is empty");
           return -1;
       }
       int item = arr[front];
       front = (front + 1) % capacity;
       count--;
       return item;
   }
   
   public boolean isEmpty() {
       return (count == 0);
   }
   

   The dequeue method retrieves the element at front, then moves the front one position forward, also wrapping with modulo.

Peek Operation

1. View the front element without removing it from the queue.

   java Copy

   public int peek() {
       if (isEmpty()) {
           System.out.println("Queue is empty");
           return -1;
       }
       return arr[front];
   }
   

   peek simply returns the front element, helping visualize the next item to be dequeued without modifying the queue state.

Implementing Queue Using LinkedList

Class Definition

1. Define a Node class and essential attributes of the LinkedList-based Queue.

   java Copy

   class Node {
       int data;
       Node next;
       Node(int data) {
           this.data = data;
       }
   }
   
   class LinkedListQueue {
       private Node front, rear;
       LinkedListQueue() {
           front = rear = null;
       }
   }
   

   A Node holds the individual data pieces and the reference to the next node. front and rear help in managing the queue ends.

Enqueue Operation

1. Add elements to the end of the linked list.

   java Copy

   void enqueue(int item) {
       Node newNode = new Node(item);
       if (rear == null) {
           front = rear = newNode;
           return;
       }
       rear.next = newNode;
       rear = newNode;
   }
   

   When enqueuing in a linked-list-based queue, add the new node at the end and adjust the rear.

Dequeue Operation

1. Remove the front node and return its data.

   java Copy

   int dequeue() {
       if (front == null) {
           System.out.println("Queue is empty");
           return -1;
       }
       int item = front.data;
       front = front.next;
       if (front == null) {
           rear = null;
       }
       return item;
   }
   

   The front node is removed, and if there are no more nodes left, the rear is also set to null.

Conclusion

Implementing queues in Java can be achieved through array or linked list approaches, each with its own way of managing the elements. The array method limits the queue's size, while the linked list offers dynamic resizing but with potentially higher memory overhead. With the examples provided, adapt the queue implementation to efficiently handle scenarios requiring FIFO data handling in your Java applications. This exploration ensures a deep understanding of queue operations and prepares you for more complex data structure implementations.