Write a Program to implement Queue using Singly linked list Python

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
Python Program to Implement Queue Data Structure using Linked List
Queue (data structure) implementation using singly linked list in Python
Linked List implementation of Queue
Basic Operation:
Queue using linked list

Python Program to Implement Queue Data Structure using Linked List

PythonServer Side ProgrammingProgramming

When it is required to implement a queue data structure using a linked list, a method to add (enqueue operation) elements to the linked list, and a method to delete (dequeue operation) the elements of the linked list are defined.

Below is a demonstration for the same −

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

Queue (data structure) implementation using singly linked list in Python

Today I’ll talk about how to implement Queue data structure using another data structure Singly linked list in Python. If you want to know how to implement Singly linked list in Python then read this previous blog post Singly linked list.

First, let’s know about Queue data structure. Queue is a particular kind of abstract type data structure, it is a FIFO (First in First out) data structure. In a FIFO data structure , an item inserted in first , will be removed first. Inserting an element in Queue is called enqueue and removing an element from it is called dequeue.

Here I’ll show you how to enqueue , dequeue and in addition - how to get the size of queue , check if queue is empty or not, and at last how to print it as a list/array.

So , let’s start coding.

I’m gonna use Singly linked list to implement Queue data structure, so according to linked list first create a Node class , by which we can create an element with a given data to be enqueued in Queue.

In the Node class, we will set the data and next_node(i.e pointer) equal to None as parameter in init method so that if we don’t send any data and pointer to the next node, it will return None. Then get_data and get_next methods will return the data and the next node respectively. We will add another method set_next which will take a new_node as a parameter and will set the pointer from previous Node towards this Node.

class Node: def __init__(self,data=None,next_node=None): self.data = data self.next_node = next_node def get_data(self): return self.data def get_next(self): return self.next_node def set_next(self,new_node): self.next_node = new_node

After that create another class named Queue, and set the head (1st element of Queue) = None as parameter in init method. Then we will insert an element at first of Queue using enqueue method. The enqueue method takes a data as parameter and create a Node using it. Now, we’ll check if there is any head in Queue! If it hasn’t one,we set the Node(new_item)/element created previously as head. If there is already a head i.e. there are elements in Queue. So, we will go to the end of Queue using while loop and when we find that pointer of the previous node is null, we set the pointer of last Node/element towards the Node we created.

class Queue: def __init__(self,head=None): self.head = head def enqueue(self,data): new_item = Node(data) current = self.head if current is None: self.head = new_item else: while current.get_next(): current = current.get_next() current.set_next(new_item)

Now it’s time to add a method dequeue to remove the first element from the Queue. First, we check whether the Queue is empty or not , if it is not empty then we set the second element of Queue as head and first element(self.head) which was initially stored in current get removed. Again, if the Queue is empty, we simply print “Queue is empty.” .

def dequeue(self): current = self.head if current != None: self.head = current.get_next() else: print("Queue is empty.")

Using dunder method len, so that we can get the size of Queue using len() over the Queue we have written.

def __len__(self): return len(self.temp)

Let’s create another method is_empty which tells us whether the Queue is empty or not! If self.head(1st element of Queue) is None i.e. there is no element it returns False , else returns True.

def is_empty(self): if self.head == None

It’ll be better if can visualize the Queue as a list/array. So, this print_queue method gets the job done. First, just set the head/1st element to current variable and create an empty list which we can store in a variable , let’s name it temp. Now, we go through the whole Queue using while loop and every time we find an element ,just append it to temp list and go to next element. At the end print temp.

def print_queue(self): current = self.head self.temp = [] while current: self.temp.append(current.get_data()) current = current.get_next() print(self.temp)

Okay,you see that we have implemented a Queue using Singly linked list in Python. It’s checking time whether the code works as expected.

q = Queue() q.enqueue("User01") q.enqueue("User02") q.enqueue("User03") q.enqueue("User04") q.enqueue("User05")

q.print_queue() >>> ['User01', 'User02', 'User03', 'User04', 'User05'] q.dequeue() q.print_queue() >>> ['User02', 'User03', 'User04', 'User05'] q.dequeue() q.print_queue() >>> ['User03', 'User04', 'User05'] print(len(q)) >>> 3 print(q.is_empty()) >>> False

That’s how you can implement a Queue data structure using Singly linked list in Python. Hope , my explanation helps the guys out there who are learning data structure using Python. Keep learning!

Please enable JavaScript to view the comments powered by Disqus.

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.

Basic Operation:

Following are basic operations of Queue:

Main Queue Operations:
1)EnQueue(): Inserts an element at the rear of the Queue.
2)DeQueue(): Remove and return the front element of the Queue.

Auxiliary Queue operation:

1)Front(): Display the data front of the Queue.
2)QueueSize(): Returns the number of elements stored in the Queue.
3)display(): Display elements of queue.

There are many different operations that we can implement.
For ex.:- Merging of Two Queue,Sorting of Queue etc..

Let's see implementation of Queue and its operations,with example.
For linked list we will make structure of Node using struct keyword.In which we here taking int data and one pointer of that struct to point another Node.
First we will take two pointers of that struct Node, front=NULL and rear=NULL.

EnQueue

Inserting an element in Queue.

Initially both of our pointers pointing to the front and rear are NULL.
Now,If We enter the 12 in Queue we will checking weather there is any element present or not.If rear is NULL,We make our front and rear pointers to point our newly inserted Node with having data '12'.
Now,again if we want to enter new data,Let say 45.We will check for rear NULL or not.Now our rear would be pointing to '12'.So 45 will added next to the rear Node and 45 would be our rear Node.
Same way if i add 26, it would be added after 45 and rear will point to the Node having data '26'.

Pseudocode:

Step 1 : Create a newNode with given value and set 'newNode → next' to NULL. Step 2 : Check whether queue is Empty (rear == NULL) Step 3 : If it is Empty then, set front = newNode and rear = newNode. Step 4 : If it is Not Empty then, set rear → next = newNode and rear = newNode.

DeQueue

Deleting an element from Queue.

Now, by doing three EnQueue operation we will be having Queue having 3 elements as shown in figure.
First we check that front is NULL?If it is then Queue is empty we can not perform DeQueue operation.But here front will be pointing to '12'.
So if we want to delete element from Queue. As our Queue is FIFO(first in first out) 12 is first inserted, so 12 will be removed.Our front pointer will be pointing to the '12'.To,remove it first we make our front pointer to point the element inserted after '12'.And then simply we free the memory.
As simple as that 45 and 26 will be removed if we perform two more DeQueue operation.And again our Queue will be empty(rear and front will be eqal to NULL).

Step 1 : Check whether queue is Empty (front == NULL). Step 2 : If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from the function Step 3 : If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'. Step 4 : Then set 'front = front → next' and delete 'temp' (free(temp)).

Display

To display all elements present in Queue, we will take one temp(you can give whatever name you want) pointer and make that to point front.
Then we traverse up-to rear or we can say temp!=NULL using temp=temp->next (which will make our pointer to move towards rear) and print temp->data.

Step 1 : Check whether queue is Empty (front == NULL). Step 2 : If it is Empty then, display 'Queue is Empty!!!' and terminate the function. Step 3 : If it is Not Empty then, define a Node pointer 'temp' and initialize with front. Step 4 : Display 'temp → data -->' and move it to the next node. Repeat the same until 'temp' reaches to 'rear' (temp → next != NULL). Step 5 : Finally! Display 'temp → data --> NULL'.