Understanding Queue Data Structure | Explanation | Real Life Examples and Implementations

Queue is a linear data structure which works on the principle of FIFO ( First In First Out ). What does this means? So, when we add any value in our queue, it will retereive in the same order as it pushed in queue. So, if we have pushed '1' in our queue firstly, so when ever we will pop the element from queue, '1' will be the element which will be popped first of all, because it pushed first. So queue always follow the principle of FIFO.

Thus, we can say that queue is a line where elements are inserted in one end (Rear) and elements are removed from other end (front). And the element which is inserted first will be the element which is to be removed first.

Important Dictionary

Now, discuss some important dictionary which we will be using while understanding our Queue Data Structures and Implementation.

• Enqueue -> Used when we want to add an element in queue.
• Dequeue -> Used when we want to remove an element from queue.
• Front -> Index, from where we will dequeue elements from queue.
• Rear -> Index, from where we will enqueue elements into queue.
• Peek -> Value, present at the front of the queue.

Basic Operations In Queue

In queue, we can implement 5 basic operations :

• Enqueue(Push) Adds an element in rear(back) of the queue.
• Dequeue(Pop) Remove an element from the front of the queue.
• Peek returns an element present at front of queue.
• Empty returns about emptiness of queue
• Full tells the queue is full now ( Only for array, LinkedLists never full )

Implementation Of Queues with Linked Lists

We have two methods for the implementation of queue.

1. Implementation of queue with Arrays
2. Implementation of queue with LinkedLists

Here, w'll be discussing how to implement queue with LinkedLists.

Note : Before starting our implementation, we should know that will be using two classes one for the Nodes to connect with next nodes, and the sesond class will be the class where we will implement our actual functions.

Node's Class Structure

Our Node Class will have 2 variables, variable named value of type integer ( to store the current's value of the node) & variable named next of type Node class ( pointer to store the address of next node ). The constructor of the class Node will initializa the node's value and next pointer will always be null, we will set it in our main functions according to our needs and requirements.

Solution Class Structure

The Solution Class will have 3 variables, variable named front of type node ( node which will be the node to remove from LinkedLists), variable named rear of type node ( node whose next will be the incoming node ) and the variable named ElementsCount of type Integer ( to count number of nodes in our linked list) .

Enqueue Function

Suppose, we have empty LinkedList. Now when we add a new element into it, our front and rear both will point to the same node, so when we will dequeue an element, the only node will be the node which we will pop.

So, Let's suppose we have our List as 1 -> null. Here, front is pointing to '1', so when we will run Enqueue( 9 ), our list will become 1 -> 9 -> null. Now, here, front will be pointing to node with value '1' because it's the node which we added first and it will be the node which we will remove first, and now rear will be pointing to the node '9', as now '9' node is the node whose next node will be our incoming new node. And when will again Enqueue( 6 ), front will remain pointing to '1', but now rear will be pointing to '6', as it's the node which added in the last and next node will be added on next of '6'. So, our array will become 1 -> 9 -> 6 -> null.

To learn more how we change pointers in LinkedList, you can view our article.

And as when will call Enqueue( element ) function, we will increment in our ElementsCount variable, which will give us total number of elements in the end.

Here, you can see if our list is empty, so front and rear both will point to the same node. Because it's the only point where we add new elements as well the point which we will remove first.

And if the list is not empty, we will increment our rear, but our fronnt will remin pointing to the node which was enqueued first, it will only change when that first node will be dequeued, and then our front will point to the node which wes added after the first node.

Dequeue Function

In the dequeue function, first of all we have to apply a check that our list should not empty. If our list is empty, it's mean that there's no element to dequeue now.

As, we know that queue follows the principle of FIFI ( First In First Out ). So, front variable will always be pointing to the node which was added first of all. And when we dequeue it, our front pointer will now be pointing to the next node. We will keep doing it, until our list becomes empty.

Note : With calling dequeue function, w'll not be passing any element as parameter, because we will remove the element which our front points to.

Let's take an example witha LinkedList as 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null. Here, front points to '1' and rear points to '6'. When we will first call Dequeue( ), node which front points will delete and our front will start pointing to next node, and our list will become 2 -> 3 -> 4 -> 5 -> 6 -> null. When we will again call Dequeue( ) function, '2' deletes and our list will becomes 3 -> 4 -> 5 -> 6 -> null. When we will again call Dequeue( ) function, '3' deletes and our list will becomes 4 -> 5 -> 6 -> null. When we again call Dequeue( ) function, '4' deletes and our list will becomes 5 -> 6 -> null. When we will again call Dequeue( ) function, '5' deletes and our list will becomes 6 -> null. Now, here rear and front both are pointing to same node. But yet the list is not empty, so we gain can call dequeue( ) function, our now front will be pointing to null. Now as front == null, means list is empty, now we can't dequeue more.

Here, one thing is important to note that, when our list was 6 -> null, here rear and front both were pointing to the same node. When we called Dequeue( ), our front moved next, and start pointing to null, but rear remains pointing to '6', which means that rear is pointing to the node, which we have deleted, so here we also have to move rear to point to null.

Peek/Front Function

This operation returns the element at the front without removing it.

The following steps are taken to perform the front operation:

• If the queue is empty return the most minimum value.
• otherwise, return the front value.

Rear Function

This operation returns the element at the rear/end without removing it.

The following steps are taken to perform the rear operation:

• If the queue is empty return the most minimum value.
• otherwise, return the rear value.

Size Function

This operation returns the total number of elements in the queue.

The following steps are taken to perform the size operation:

• If the queue is empty return the 0.
• otherwise, return the Elementscount variable's Value.

Empty Function

This operation returns that list is empty or not.

The following steps are taken to perform the Empty operation:

• If the front is pointing to null, this means there's no element and return true.
• otherwise, return the false.

Practical Application of Queue

One practical application of a queue is task scheduling in operating systems.

In multitasking operating systems, processes or tasks are managed using queues. The system schedules tasks in a "First In, First Out" (FIFO) manner, meaning the first task to enter the queue gets processed first. This ensures that every process gets a fair chance to execute and that resources are efficiently allocated. For example, when printing multiple documents, they are stored in a print queue, where the first document sent is printed before the next one.

Resources

• GitHub Repository View Complete Implementation of Queue with Linked Lists also with Arrays in this reposotory.
• DSA in CpluPlus View the GitHub Repository to check and to analyze how to complete DSA in C++
• DSA in Python If you want to continue with DSA in Python, I mentioned LeetCode Question Solved in Python using DSA.
• Lecture On Stack Implementation with Arrays You can also view my lecture on Implementation of Stack with arrays on YouTube.
• Solved leetCode Questions About Queue with Python You can also view my Solved LeetCode questions of Queue Data Structure.

#PostfixEvaluation #StackApplications #DataStructures #BackendDevelopment #ExpressionEvaluation #TechExplained #ProgrammingConcepts #ComputerScience #CodeEducation #DeveloperJourney #CodingSkills #AlgorithmicThinking #MathematicsInProgramming #SoftwareEngineering #TechEducation #DSA