This article is con-centered in the implementation of Queue using a Linked List in Python Programming Language. Also Read: Creating Singly Linked List in Python Programming Language.
What are Queues?
A Queues is an abstract data structure where we can add new items and remove items from two ends (Front and Rear). The process is verbalized as Enqueueing and Dequeuing, respectively.
Consider an example of a physical line of people: People can be added to the end of the line called (enqueuing), and people are removed from the front of the line called (dequeuing). An exactly this way, the queue system works in the real world. If you go to a ticket counter to buy bus tickets and are first in the queue, then you will be the first one to get the tickets. Right? Same is the case with Queue data structure. Data inserted first will leave the queue first. This concept is described as a term called FIFO, which stands for first in, first out. It is a data structure where the first element added to the collection will be the first removed.
Basic features of Queue
Applications of Queue
The queue is used to manage any group of objects in an order of FIFO and other elements for their turn, like in the following scenarios:
Implementation of Queue using Linked List (Code)
A queue can be implemented using an Array, Stack or Linked List but the easiest way is the array method. We are not concerned about the array implementation here, we will see the linked list representation.
Code: The algorithm used to implement the queue using linked list is: I will be storing a reference to the front and back of the queue in order to make the enqueuing and dequeuing run in O(1) constant time. Every time when I want to insert into the queue, I add the new element to the end of the linked list and update the back pointer. When I want to dequeue, I return the first node in the linked list and update the front pointer.
Output: Here We can see that the first element ‘a’ that was inserted first also popped out from the queue first.
