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.
Python Program to Implement Queue Data Structure using Linked List
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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(); dequeue(); dequeue(); 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.
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.
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.” .
Using dunder method len, so that we can get the size of Queue using len() over the Queue we have written.
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.
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.
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.
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!
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:
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).
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.
Queue using linked list
Queue using an array - drawback
If we implement the queue using an array, we need to specify the array size at the beginning(at compile time).
We can't change the size of an array at runtime. So, the queue will only work for a fixed number of elements.
Solution
We can implement the queue data structure using the linked list.
In the linked list, we can change its size at runtime.