Queue implementation in Java
In this post, you will learn how to implement a Queue using the Java programming language.
A queue is a linear data structure where insertion of elements is done from one end and deletion from the other end. The queue is like a line of people at a polling booth where the first person in the line gets the first vote. This is called First-In-First-Out (FIFO). Insertion of the element is done from the one end, called the FRONT end and deletion is done from the other end, called the REAR.
Queue Operations
These are the operations performed by a queue.
- Enqueue - The element to add in a queue. If the queue is full, then it is said to be an overflow condition.
- Dequeue - The element to delete in a queue. If the queue is empty, then it is said to be an underflow condition.
- Peek- Retrieve the element from the front end of the queue without removing it from the queue.
- IsEmpty- Check if the queue is empty or not.
- Size- Return the total number of elements present in the queue.
- Front- Get the front item from the queue.
- Rear- Get the last item from the queue.
Algorithm to Insert Element in a Queue
Step 1: IF REAR = MAX-1
print('Queue Overflow')
return
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT
In the above algorithm, we have checked the existence of space in the queue. If there is no space then print 'Queue Overflow' and the code is exited and if not then, we check the element at the FRONT and REAR, if both are empty then set both to 0 else increase REAR with one and insert element from the REAR end and return.
Algorithm to Delete Element in a Queue
Step 1: IF FRONT = -1 OR FRONT > REAR
print('Queue Underflow')
return
ELSE
SET FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT
In the above algorithm, we have checked the existence of elements in the queue. If there is no element, then print 'Queue Underflow' and the code is exited; if not, then FRONT is increased by one and points to the next element in the queue.
Queue Implementation in Java using an array
Here is the program to implement queue using an array in Java.
// A class to represent a queue
class Queue
{
// array to store queue elements
private int[] arr;
private int front;
private int rear;
private int capacity;
private int count;
// Constructor to initialize a queue
Queue(int size)
{
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
count = 0;
}
// function to dequeue the front element
public int dequeue()
{
// check for queue underflow
if (isEmpty())
{
System.out.println("Queue Underflow");
System.exit(-1);
}
int x = arr[front];
System.out.println("Removing element : " + x);
front = (front + 1) % capacity;
count--;
return x;
}
// function to add an item to the queue
public void enqueue(int item)
{
// check for queue overflow
if (isFull())
{
System.out.println("Queue Overflow");
System.exit(-1);
}
System.out.println("Inserting element : " + item);
rear = (rear + 1) % capacity;
arr[rear] = item;
count++;
}
// function to print the front element of the queue
public int peek()
{
if (isEmpty())
{
System.out.println("Queue Underflow");
System.exit(-1);
}
return arr[front];
}
// function to return the size of the queue
public int size() {
return count;
}
// function to check if the queue is empty
public boolean isEmpty() {
return (size() == 0);
}
// function to check if the queue is full
public boolean isFull() {
return (size() == capacity);
}
}
public class Main
{
public static void main (String[] args)
{
// Initialize a queue of capacity 5
Queue q = new Queue(5);
// insert elements in the queue
q.enqueue(11);
q.enqueue(98);
q.enqueue(40);
q.enqueue(52);
q.enqueue(71);
System.out.println("The front element : " + q.peek());
q.dequeue();
System.out.println("The front element : " + q.peek());
System.out.println("The queue size : " + q.size());
q.dequeue();
q.dequeue();
if (q.isEmpty()) {
System.out.println("The queue is empty");
}
else {
System.out.println("The queue is not empty");
}
}
}
Output of the above code:
Inserting element : 11
Inserting element : 98
Inserting element : 40
Inserting element : 52
Inserting element : 71
The front element : 11
Removing element : 11
The front element : 98
The queue size : 4
Removing element : 98
Removing element : 40
The queue is not empty
Queue Implementation in Java using Linked list
The linked list is a non primitive data structure which is free from fixed memory size restrictions. It is static free and the user can add any number of elements when required. We can use this to create other data structures like stacks, queues, etc. It allows the insertion and deletion of nodes at any point in the list.
Here, we will discuss the implementation of Queue using Linked List in Java programming. In the linked queue, there are two pointers maintained in the memory, i.e., front and rear. The front pointer contains the address of the starting element of the queue, while the rear pointer contains the address of the last element of the queue.
// A Linked List Node
class ListNode
{
int data;
// set pointer to the next node
ListNode next;
public ListNode(int data)
{
// Creates a node storing the specified data.
this.data = data;
this.next = null;
}
}
class Queue
{
private static ListNode rear = null, front = null;
private static int count = 0;
// function to dequeue the front element
public static int dequeue()
{
// check for queue underflow
if (front == null)
{
System.out.println("\nQueue Underflow");
System.exit(-1);
}
ListNode temp = front;
System.out.printf("Removing element : %d\n", temp.data);
// advance front to the next node
front = front.next;
// if the list becomes empty
if (front == null) {
rear = null;
}
// decrease the node's count by 1
count -= 1;
return temp.data;
}
// function to add an item to the queue
public static void enqueue(int item)
{
// allocate a new node
ListNode node = new ListNode(item);
System.out.printf("Inserting element : %d\n", item);
// check for empty queue
if (front == null)
{
// initialize both front and rear
front = node;
rear = node;
}
else {
// update rear
rear.next = node;
rear = node;
}
// increase the node's count by 1
count += 1;
}
// function to return the top element in a queue
public static int peek()
{
// check for an empty queue
if (front == null) {
System.exit(-1);
}
return front.data;
}
// function to check if the queue is empty or not
public static boolean isEmpty() {
return rear == null && front == null;
}
// function to return the size of the queue
private static int size() {
return count;
}
}
public class Main
{
public static void main(String[] args)
{
Queue q = new Queue();
q.enqueue(61);
q.enqueue(21);
q.enqueue(41);
q.enqueue(51);
System.out.printf("\nThe front element : %d\n", q.peek());
q.dequeue();
q.dequeue();
q.dequeue();
if (q.isEmpty()) {
System.out.println("The queue is empty");
}
else {
System.out.println("The queue is not empty");
}
}
}
Output of the above code:
Inserting element : 61
Inserting element : 21
Inserting element : 41
Inserting element : 51
The front element : 61
Removing element : 61
Removing element : 21
Removing element : 41
The queue is not empty
Related Articles
Sort array in ascending order JavaAutomorphic number in Java
Pascal triangle program in Java
Factorial using recursion in java
Java random number between 1 and 10
Palindrome program in Java
Floyd triangle in Java
Pyramid pattern programs in Java
Star pattern programs in Java
Number pattern programs in Java
Java program to find area of rectangle
Matrix multiplication in Java
Electricity bill program in Java
Java program to find area of triangle
Area of circle program in Java
Remove duplicate elements from array in Java
Capitalize first letter of each word Java
Convert binary to decimal in Java
Convert decimal to binary in Java
Convert decimal to octal in Java
Convert decimal to hexadecimal in Java
Simple interest program in Java