A queue is a linear data structure that follows the First In, First Out (FIFO) principle, which states that the element inserted first will be removed first. This concept is similar to real life circumstances such as people standing in a line, printing jobs sitting in a queue, and tasks scheduled for processing.
A queue in Java can be constructed with arrays, linked lists, or built-in Java Collections Framework classes. In this article, we will go over how to create a queue data structure in Java from scratch, as well as how to use Java’s built-in Queue.
What is the Queue in Data Structure ?
Queue is a fundamental concept of managing and storing data in the data structure ( linear data structure ).
Queue is opened from both the end that makes it flexible and fast for inserting and deleting elements in data structure .
There are different terminologies that we are using in queue to understand its representation :
- Enqueue ( Insertion operation in queue )
Enqueue operation of queue inserts elements in a queue. Insertion of elements in the queue done from the rear end.
- Dequeue ( Deletion operation in queue )
Deletion operation of the queue removes elements from the queue. Deletion will be done from the front end of the queue.
The representation of the queue looks like the arrangement of elements in the list where both the ends are opened. Pictorial representation of the queue in data structure depicted below :
There are some cases when we are performing deletion and insertion in a queue . We have to consider two pointers in the queue i.e, front pointer and rear pointer.
Case 1 : If queue is empty ( there is no element in queue )
Front > Rear or Front = Rear = -1
Case 2 : If queue is not empty ( there is at least one element in the queue )
Front < Rear
Case 3 : If there is only one element in the queue
Front = Rear
Case 4 : For enqueue operation
Rear = Rear + 1
Implementation of Queue Data Structure in Java
public class ArrayQueue {
private int front, rear, capacity;
private int queue[];
public ArrayQueue(int size) {
front = 0;
rear = 0;
capacity = size;
queue = new int[capacity];
}
public void enqueue(int data) {
if (rear == capacity) {
System.out.println("Queue is full");
return;
}
queue[rear] = data;
rear++;
}
public void dequeue() {
if (front == rear) {
System.out.println("Queue is empty");
return;
}
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
rear--;
}
public void display() {
if (front == rear) {
System.out.println("Queue is empty");
return;
}
System.out.print("Queue: ");
for (int i = front; i < rear; i++) {
System.out.print(queue[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
ArrayQueue q = new ArrayQueue(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.display(); // Output: Queue: 10 20 30
q.dequeue();
q.display(); // Output: Queue: 20 30
}
}
Implementation of Queue Data Structure in Java Using Linked List
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedListQueue {
Node front, rear;
public LinkedListQueue() {
this.front = this.rear = null;
}
public void enqueue(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
return;
}
rear.next = newNode;
rear = newNode;
}
public void dequeue() {
if (front == null) {
System.out.println("Queue is empty");
return;
}
front = front.next;
if (front == null) rear = null;
}
public void display() {
Node temp = front;
System.out.print("Queue: ");
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedListQueue q = new LinkedListQueue();
q.enqueue(5);
q.enqueue(15);
q.enqueue(25);
q.display(); // Output: Queue: 5 15 25
q.dequeue();
q.display(); // Output: Queue: 15 25
}
}
Frequently Asked Questions
What is a queue in Java?
A queue in Java is a linear data structure that follows the FIFO (First-In-First-Out) principle, where elements are inserted at the end and removed from the front.
How do you implement a queue using an array in Java?
You create an integer array and maintain two indices front and rear to track insertion and removal. Be mindful of size constraints and overflows.
Can we use LinkedList as a queue in Java?
Yes, LinkedList implements the Queue interface and can be used to create a queue easily using built-in methods like add(), remove(), and peek().
What are the advantages of using a queue?
Queues help manage data in an ordered way, suitable for scheduling tasks, BFS in graphs, and real-time data processing.
What is the time complexity of queue operations?
In an array-based queue:
- enqueue – O(1)
- dequeue – O(n) (due to shifting)
In a linked list-based queue: - enqueue and dequeue – O(1)
How does Java handle empty or full queues?
When using arrays, you need to manually handle full/empty states. In LinkedList, if you remove from an empty queue, it throws a NoSuchElementException.
What is the difference between Stack and Queue?
Stack follows LIFO (Last In First Out), while Queue follows FIFO (First In First Out).
Which Java classes implement the Queue interface?
Common classes include LinkedList, PriorityQueue, ArrayDeque.
How do I peek the front of a queue in Java?
Use the peek() method in Java Collections, or return the front node/value in custom implementations.
When should you prefer a linked list over an array for queues?
Use a linked list when you expect a lot of insertions/removals and don’t want to worry about size constraints or shifting elements.