Implement queue using linked list
In this post, you will learn how to implement a Queue using linked list in different 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 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", and deletion is done from the other end, called "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 queue.
- Rear - Get the last item from queue.
The linked list is a non primitive data structure that 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.
Queue Implementation using linked list in C++
Here is the C++ program for queue implementation using linked list.
The function enqueue() inserts an element into the queue. Initially, it checks if rear is NULL, then the queue is empty and a single element is inserted. Otherwise, a node is inserted after the rear with the required element, and then that node is set to rear.
In the function dequeue(), firstly check if the queue is empty. If it is, then print the result as "Queue Underflow". If there is only one element in the queue, that is deleted, and the front and rear are set to NULL. Otherwise, the element at the front is deleted, and the front points to the next element.
In the function show(), if front and rear are NULL then queue is empty. Otherwise, using a while loop, print all the queue elements starting from front to rear with the help of the temp variable.
#include <iostream>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;
void enqueue() {
int val;
cout<<"Enter value to inset in queue : ";
cin>>val;
if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node));
rear->next = NULL;
rear->data = val;
front = rear;
} else {
temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp;
temp->data = val;
temp->next = NULL;
rear = temp;
}
}
void dequeue() {
temp = front;
if (front == NULL) {
cout<<"QUEUE UNDERFLOW!"<<endl;
return;
}
else
if (temp->next != NULL) {
temp = temp->next;
cout<<"Element deleted from queue : "<<front->data<<endl;
free(front);
front = temp;
} else {
cout<<"Element deleted from queue : "<<front->data<<endl;
free(front);
front = NULL;
rear = NULL;
}
}
void show() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"QUEUE UNDERFLOW!"<<endl;
return;
}
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
int main() {
int choice;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : ";
cin<<choice;
switch (choice) {
case 1: enqueue();
break;
case 2: dequeue();
break;
case 3: show();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(choice!=4);
return 0;
}
Output of the above code:
1) Insert element to queue
2) Delete element from queue
3) Display all the elements of queue
4) Exit
Enter your choice : 1
Enter value to inset in queue : 39
Enter your choice : 1
Enter value to inset in queue : 90
Enter your choice : 3
39 90
Enter your choice : 2
Element deleted from queue : 39
Enter your choice : 3
90
Enter your choice :
Queue Implementation in Java using Linked 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
Queue Implementation in Python using Linked list
Here is the source code of a Python program to implement a queue using a linked list.
class Node:
def __init__(self, data):
self.data = data
self.next = None
# A class to represent a queue
class Queue:
def __init__(self):
self.front = self.rear = None
def isEmpty(self):
return self.front == None
# Method to add an item to the queue
def EnQueue(self, item):
temp = Node(item)
if self.rear == None:
self.front = self.rear = temp
return
self.rear.next = temp
self.rear = temp
# Method to remove an item from queue
def DeQueue(self):
if self.isEmpty():
return
temp = self.front
self.front = temp.next
if(self.front == None):
self.rear = None
# Driver Code
if __name__== '__main__':
q = Queue()
q.EnQueue(13)
q.EnQueue(22)
q.DeQueue()
q.DeQueue()
q.EnQueue(12)
q.EnQueue(82)
q.EnQueue(71)
q.DeQueue()
print("Queue Front " + str(q.front.data))
print("Queue Rear " + str(q.rear.data))
Output of the above code:
Queue Front 82
Queue Rear 71
Related Articles
Implementation of queue using array in CQueue implementation in Python
Queue Implementation in C
Capitalize first letter of each word Java
Convert binary to decimal in Java
Convert array to list Python
Python take screenshot of specific window
Web scraping Python BeautifulSoup
Check if two strings are anagrams Python
Python program to add two numbers
Print new line python
Prime factors of a number in c
Armstrong number program in c
Write a program to check leap year in c
C program to find area of rectangle
C program to convert celsius to fahrenheit
Fibonacci series program in C using recursion
Write a program to find area of circle in C
C program to convert Decimal to Octal
C program to convert decimal to binary
C program to check whether a number is even or odd