Write a Java program to implement the queue adt using a singly Linked list

Queue – Linked List Implementation

In the previous post, we introduced Queue and discussed array implementation. In this post, linked list implementation is discussed. The following two main operations must be implemented efficiently.
In a Queue data structure, we maintain two pointers, front and rear. The front points the first item of queue and rear points to last item.
enQueue() This operation adds a new node after rear and moves rear to the next node.
deQueue() This operation removes the front node and moves front to the next node.

Table of Contents Show

Queue – Linked List Implementation
Java Program to Implement the queue data structure
Linked List implementation of Queue

C

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

#include <stdio.h>

#include <stdlib.h>

// A Linked List Node

struct Node

{

int data; // integer data

struct Node* next;// pointer to the next node

}*rear = NULL, *front = NULL;

// Utility function to allocate the new queue node

struct Node* newNode(int item)

{

// allocate a new node in a heap

struct Node* node = (struct Node*)malloc(sizeof(struct Node));

// check if the queue (heap) is full. Then inserting an element would

// lead to heap overflow

if (node != NULL)

{

// set data in the allocated node and return it

node->data = item;

node->next = NULL;

return node;

}

else {

printf("\nHeap Overflow");

exit(EXIT_FAILURE);

}

// Utility function to dequeue the front element

int dequeue()// delete at the beginning

{

if (front == NULL)

{

printf("\nQueue Underflow");

exit(EXIT_FAILURE);

}

struct Node* temp = front;

printf("Removing %d\n", temp->data);

// advance front to the next node

front = front->next;

// if the list becomes empty

if (front == NULL) {

rear = NULL;

}

// deallocate the memory of the removed node and optionally return the removed item

int item = temp->data;

free(temp);

return item;

}

// Utility function to add an item to the queue

void enqueue(int item)// insertion at the end

{

// allocate a new node in a heap

struct Node* node = newNode(item);

printf("Inserting %d\n", item);

// special case: queue was empty

if (front == NULL)

{

// initialize both front and rear

front = node;

rear = node;

}

else {

// update rear

rear->next = node;

rear = node;

}

// Utility function to return the top element in a queue

int peek()

{

// check for an empty queue

if (front != NULL) {

return front->data;

}

else {

exit(EXIT_FAILURE);

}

// Utility function to check if the queue is empty or not

int isEmpty() {

return rear == NULL && front == NULL;

}

int main()

{

enqueue(1);

enqueue(2);

enqueue(3);

enqueue(4);

printf("The front element is %d\n", peek());

dequeue();

if (isEmpty()) {

printf("The queue is empty");

}

else {

printf("The queue is not empty");

}

return 0;

}

DownloadRun Code

Java Program to Implement the queue data structure

In this example, we will learn to implement the queue data structure in Java.

To understand this example, you should have the knowledge of the following Java programming topics:

Java Queue Interface
Java Generics

Linked List implementation of Queue

Due to the drawbacks discussed in the previous section of this tutorial, the array implementation can not be used for the large scale applications where the queues are implemented. One of the alternative of array implementation is linked list implementation of queue.

The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory.

In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. 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.

Insertion and deletions are performed at rear and front end respectively. If front and rear both are NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.