Yo, what's going on guys, Tanmay here for Simple Snippets and welcome back to another video tutorial under data structures and algorithms. So in this video tutorial we are going to be taking a look at the queue data structure and again just like the stack data structure we are going to be dividing this queue data structure in two parts. So this video is going to be all about what exactly is a queue data structure. the working of this data structure, the operations and applications.
And the second part of this would be the actual implementation in C++ program where we implement the queue and the queue operations in C++ programming language. So just like the part one of stack data structure which we had in this tutorial series, by the way if you have missed that, I will drop a link to the entire data structures and algorithms playlist in the video description and you can probably also see a card. So if you want you can go check that out. But coming back to today's topic, just like stack data structure what we will do is we will first take a theoretical understanding of queue data structure but along with the theoretical understanding we will also go to the digital blackboard and see what happens in memory behind the scenes and how exactly does a queue data structure visually look like okay so that will be very interesting and then you will understand things much better lastly we will also see the operations that is the standard queue data structure operations and we will also write the algorithm or you can see the pseudocode in this video itself so that in the part 2 we can directly jump to the coding part.
So make sure you watch this video till the end because there is a lot of information that you will get in this video and with that being said let's get started. So starting off with a little bit of theory on Q data structure what exactly is a Q data structure. Now the definition would go as follows. So Q is a linear data structure just like stack and by linear data structure I mean that the data is inserted or retrieved in a particular sequential fashion.
So it has to be linear. You'll understand this term linear more when we actually see the nonlinear types also as we move along in this series. Now this queue data structure operates in first in first out or last in last out manner.
So this is where the queue data structure is different than stack. Both stack and queue are linear data structures but stack operates as first in last out or last in first out. But queue data structure operates as first in first out or Last in last out which means that whichever item or value is stored first in a queue has to come out first okay. So this is opposite to what happens in stack right whichever value goes inside a stack comes out last.
Now the reason why it is named as a queue is because it behaves like a real world queue so the word queue itself means that there is a line formation and things happen first come first serve right. For example a queue line of a car in a single lane so as you can see on the screen over here If this is a single lane road, the first car to exit would be this orange one which is first in line, right? Then the second one and then the third one. Another example would be people walking or people waiting at a food counter in a particular queue or people waiting for a doctor's appointment. So there is always a numbering and typically it is first come first serve, right?
So whatever or whoever comes first has to go first. So that's why it is known as a queue data structure. Now again, it is an abstract data type.
with a bounded or predefined capacity. We've already talked about abstract data types. And it's a simple data structure that allows adding and removing elements in a particular order.
And this order is first in first out. Of course, this first in first out will be more clear when we actually visually take the diagrammatic representation. So the order is first in first out or another way to put it is last in last out.
So this was a little bit of theory on Q data structure. And this would give you a very basic understanding of how real world scenarios also look like. But now let's jump to the digital blackboard and see what happens behind the scenes when it comes to the digital representation or the data structures representation of a Q data structure.
Okay, so as you can see in the screen, what I have represented over here in this matrix format is basically the computer memory, you can consider this as RAM. And we know that each memory location has its unique address. So let's say this is hash 1000, this is as 1001, and so on and so forth. So when you create a Q data structure.
in the memory this is how it would look like so what we are currently doing over here is we are saying we want a queue with a size of 4 you can see 1 2 3 and 4 the orange rectangular box so i'm gonna say queue of size 4 okay so this registers a queue of size 4 and this is something that visually it would look like okay in the computer ram or computer memory now queue always has a start and end so it is represented by a front or head or rear and back. So basically there are two important operations when it comes to Q that is called the NQ operation and DQ. Okay, now we already know that Q is a linear data structure which operates in first in first out our last in last out mode. The two more important points to remember are elements are added at one end. This is called NQ and elements are removed from other end.
This is called DQ. Now this is not similar to stack you know in stack we had something like this and elements were added also from one end and removed from also from this top and only right because this end was closed but here if you see So, I have represented this entire queue separately over here. Here you can see we have two ends over here. Okay. Now depending on from where you insert the first value that would be known as the rear.
Okay. Elements are added at one end which is the rear end. So let's consider this one as rear end over here. So elements would be added from over here and they would be removed from the other end because the other end is also open ended. Right.
So this is also open and this is also open. So then the remote. they are removed from other end which is the front end so this is the front and this is the rear okay so when it is inserted when the value is inserted at rear end it is called nq remember this term and whenever it is removed it is called dq okay fair enough so let's say if i insert a value phi it would be inserted over here and it would be coming directly over here okay at the start of the front that is the front end side and whenever it is it will be removed this would be made zero or null or whatever and it will be removed from over here okay Similarly, when you perform two or three NQ operations, let's say after five, I insert one, so one would come over here, five would be here.
If I insert two, it would come over here and so on and so forth. Okay, so I hope you can visually imagine how a queue would be in the memory. Okay, this is how the operations would go like.
But now let's see more in detail how the operations would look like. That is the actual standard queue operations. And we'll also try to understand the algorithm that is the pseudocode.
and how the steps would look like when you perform these different standard operations. So we have five standard operations over here, we can actually have a few more that is peak and change, but those are not really very relevant over here, we're going to be implementing these five different operations. The first one is NQ, which means elements are added from one end. So let's say this is the rear and this is the front.
Okay, so from here, when we add things, it would be NQ. DQ is elements are removed from one end. We just saw that. So when things would be removed over here, it would be DQ. The third one is is full.
Now as the name suggests, we are going to check if the queue is full or not. Now the reason why I have opening and closing parentheses is when we actually implement these operations in terms of implementation in terms of a program, we will write different functions for them. Okay, so that's why I've already denoted them in opening and closing round brackets.
The next thing is is empty as the name suggests if the Q is empty, let's say there's nothing inside, then we say it's empty. Of course, we will see what are the different conditions in a minute and how to actually check for these different conditions. And lastly, we have the count that is how many values are actually there inside the queue.
Now here the queue size is four. But let's say there are only two values inside, right? Let's say we have five and six. So currently, the count is going to be two.
Okay, so the count keeps on changing, depending upon the NQ and DQ operations where the size is going to be constant. okay now let's see the different algorithms behind these individual operations okay so before we start off with the different operations we have to do a particular initialization now when we are going to be implementing this queue in the next part that is in the program for implementing queue we are going to be using arrays okay now there are different ways in which you can actually implement queue or stack also like you can do it with another data structure which is known as linked list but since we haven't yet studied that we're going to go the simple route we are going to use arrays to implement queue just like we used array to implement stack and here the initialization is as follows so the first thing we are going to do is we are going to say int arr of 4 which means that our array size is 4 and it is a integer type array okay so this is that representation right now over here now since we know that elements are added from one end that is the rear end and they are removed from another end we need to have two different individual variables which are going to be keeping a track of the index positions In stack, we only had one end, right? We only had the top, which was keeping a track of the top of the stack. But in queue, you can see that since elements are added at one end and removed at another, we have to keep a track of both the ends.
Now, things would be more clear when we move ahead and see the actual algorithm. But right now, just keep in mind that initially what we will do is we will say rear and front equals to minus one. Okay. Now, remember that these are not pointers these are simple variables which are just keeping a track of this index location. So minus one would be somewhere over here which is not exactly a valid index location right in arrays index start from zero.
So right now let's say For rear, I'm going to say R and for front, I'll say F. So this is the initial part that we have to do when you create a queue data structure. And now let's see the individual operations. So the first operation is empty.
Now here we simply check if the front value is equal to minus one and the rear value is equal to minus one because when the initialization happens, front and rear are going to be set to minus one, right? Which means that nothing is going to be there in our array that is. Nothing is going to be there in our queue. So it will return true and this would indicate that our queue is empty. Simple enough.
This seems very basic, right? Let's see another operation that is is full. Now in is full what we're checking for is if the rear equal equal to size of ARR minus one return true.
Now what happens is when you add a new value, the rear pointer has to be incremented or the rear variable has to be incremented to keep a track. So basically currently you can see rear is pointing minus one. So let's say I perform an enqueue operation.
I say enqueue and I insert a value phi. Okay, so this phi would be stored over here, right? So it would be completely inserted and taken to the front of the queue.
So this is the front end, right? This is front and this is rear. So whenever an enqueue operation happens, we have to say rear plus plus Okay, so currently rear is minus one.
So now the rear would be pointing this one also For the first time that is when the first value is inserted, we also have to say f++ which means that the f variable or front value will also point to the first location because when the first time the first value is inserted in the queue, the rear and the front is basically one and the same. Whenever there is one more enqueue operation happening, let's say I enqueue 3 and 3 is coming over here, now the front and rear are different. Now the rear would be again plus plus and rear would be pointing to this location that is 1. So from minus 1 first NQ operation we did R plus plus and F plus plus.
So R and F become 0 and 0 right. They were pointing 0 and 0. For the second NQ operation only R is going to be incremented because now the front and rear are different. The value at the front is 5. The value at the rear is 3 right.
So there are two different ends now. I hope you are understanding this. So that's why when you are checking for isFull, we only check for the rear value.
And we check that if rear equal equal to size of ARR minus 1. Now here you can see the size is 4. Size equal to 4. If you perform 4 enqueue operations, the rear value R would have number 3 as stored in it, which is 1 less than 4. So that's why you have to check if rear equal equal to size of ARR minus 1. Okay. And if it is true, you have to say it is full. So this is the isFull operation.
I hope you have understood this and things will get more clear when we actually see the enqueue and dequeue operation also. So let's see the enqueue and dequeue operation. Okay, so this is the enqueue operation.
Now it says that first we have to check if the queue is full or not. Obviously, you cannot add more values inside the queue if the queue is entirely full, right? So the first thing that you have to do is you have to check if the queue is full. Now we just saw the algorithm for isFull.
So this is the pseudocode. Now if it is full, Obviously, you have to not proceed ahead. You have to return from over here. You have to exit this method or exit this operation.
And you have to print a message that Q is full or Q overflow or something like that, right? So if this condition is not true, you have to check for one more condition, which is if is empty. Now, the reason why I have to check for this is empty is because when the Q is empty, remember that the rear pointer and the F pointer, that is front pointer, and I'm calling it pointer, but it is not exactly a pointer.
It's a variable. is going to be storing a value of minus 1 which is not a valid index location. So whenever it is empty remember we are checking for front equal equal to minus 1 and rear equal equal to minus 1. So when you're performing an enqueue operation if it is empty the first thing that we have to do is we have to increment this rear pointer and front pointer by plus plus so that it points to or it stores a new value of the index location of 0 okay.
And the third condition is if there is some already existing value then you have to just do rear plus plus so you have to increment this let's say we already had some value over here one then you only had to increment this r plus plus right and at the end of this function you actually enqueue the value okay so if i say enqueue so you have to pass some argument in the enqueue function when you actually implement it if i say enqueue phi and let's say if our queue is empty for the starters so what will happen R will get plus plus, F will get plus plus and they will both store the new index value of 0 this else will not be executed because this else if got executed because for the first time the queue was empty right so this part got executed and at the end we are saying arr of rear which means that arr of 0 because r has now become 0 right r is storing 0 at this point we store the value and that is 5 so i'm going to store 5 over here okay let's do one more nq so i'm going to say e n q u e u e and here i'm going to say 3 so now again what will happen we will pass 3 over here we will check if is full obviously it is not full because the rear is not equal to size of arr minus 1 what is the value currently that is rear storing 0 right so this is the value now 0 is not equal equal to the size of arr minus 1 that is it is not equal to 3 0 not equal to 3 right so obviously the q is not full which means that this part the if part is not gonna get executed right Let's move on to the else if part. Now here we are checking for is empty. Here we are checking rear equal to front equal to zero. But we know that in is empty, we check if the front or rear is equal equal to minus one. Now after performing the first NQ operation, the rear and the front has become zero, which means that this will return false.
So it is not empty, right? So even this part else if part is not going to get executed, which means essentially, the last else part is going to be executed. and the else part says rear++. So we will have r++ and now the r is going to store 1. Once we increment the r++, we are saying arr of rear equals to value. So then this new value 3 that we passed is going to be stored at arr of 1. So 3 goes over here.
So f is currently 0, r is currently 1. Let's perform one last enqueue operation. So I'm going to say enqueue 2. So the value that we are passing in the NQ operation is 2. Again it is going to check isFull. The isFull condition is if rear equal equal to size of ARR minus 1. Rear over here is 1. Is 1 equal to 4 minus 1 which is 3? No right. 1 is not equal to 3. So this means the first if is not going to get executed.
Let's see what happens in else if. Here we are checking is it empty? Is the entire queue empty? For that we need to check for this part that is if front equal equal to minus 1 and rear equal equal to minus 1 but now we know that f equals to 0 and r equals to 1 so here false is going to be returned which means that else if is also not going to get executed so lastly only the else part is left so here what is happening rear plus plus so now r equals to 2 so this index location is stored in the rear and lastly we are saying arr of rear equals to value so now we are adding 2 at this location which is pointed by rear variable. Okay, so this was the complete enqueue operation.
I hope you've understood we performed three different enqueue operations. And this is basically the pseudocode. This is not the exact syntax.
But this is pretty similar of how it would look like in a C++ program also. Okay, so now let's see the last operation that is the dequeue operation. Now in the dequeue operation, what we have to do is, first of all, obviously, we'll have to check if the queue is empty or not, right?
If the queue is empty, obviously, we cannot remove more values, right? Because it is already empty. what are we going to remove right so here what i'm creating is i'm creating a temporary int x variable i'll tell you why we need that step two we are checking if the queue is empty now in is empty we check if front is equal equal to minus one and rear is equal equal to minus one obviously since we have already performed three nq operations you can see we have five three and two so the front is storing zero and rear is storing two right which means it it is definitely not empty so this if part is not gonna get executed Let's see what happens for the else if part. Now in the else if part, I have a condition which says if front equal equal to rear.
So when will this condition ever happen? Or when will this condition ever be true? This condition will ever be true if the value stored inside F is equal to value stored inside rear. Now remember this happened for the first time when we inserted one value, when R was also equal to zero and F was also equal to zero.
And this only happens when there is only one single element in the queue, right? whenever f and r are going to be equal and not equal to minus 1 because we have denoted minus 1 as an invalid state, invalid index which denotes empty. Other than minus 1, if r and f are going to be equal, it would indicate that there is only one value in the queue, right? So, in that case, what I'm doing over here is I have to remove that one single value. It would mean that there is one value left and dq always removes that value, right?
So, I'm storing that value. I'm going to say arr of front. So whatever the index location is, I'm taking the value at that index location, storing it in x variable that I created on top over here.
I'm saying front equal to rear equal to minus one. The reason why I'm doing this is because I know that when front and rear are equal to each other, it would mean that there is only one item in the queue. And when I do that, I have to make front and rear as minus one, I have to make the queue empty, right?
And the condition for empty queue is minus one. So that's why I do that over here. And then if else if is going to be executed, this else part will not be executed, right, this part will not be executed. So from else if we will directly jump to the last line of code, which is return x.
So x has stored the last value and I'm popping that off or I'm dequeuing it and removing it from the queue, right? So that's why I have to return that value. So this condition that is the else if condition is only for one special case that is when there is only one single value in the queue.
Okay, now let's see the last condition that is the else condition. So the else condition is for when there are some values more than one but not full. So the queue is not full but it also doesn't have one single value. It has multiple values just like the current queue is having three values, right? So in that case, what we do is we say x equals to arr of front because the front value has to be removed, right?
Not the rear value. Inserting is going to happen from rear end and removal is going to happen from front end. So I'm going to say arr of front equals to x.
So here currently f is equals to 0. So the value at 0 index is 5. So that I'm storing in x. I'm saying front plus plus which means now front is also going to be incremented. So when I say f plus plus f becomes one right.
So now f is pointing the second location in the array and this has become or this has removed this has been removed from the queue. Now when I say removed what we can do is we can make it zero also over here arr of front equals to zero and then we can do front plus plus. That's what we'll do in the coding part.
But essentially what we are doing is we are incrementing the front variable by one. Okay, so this is one DQ operation. Let's do one more DQ operation. So I'm going to say DQ again what is going to happen it is going to check for is empty, it's not empty because we have three and two still are is pointing over here. F is pointing over here.
That is F is having this index value R is having this index value. Again, we are checking for if front and rear are equal that is also not equal F is one and R is two. which means what will happen is again the value at the front that is error of front error of front is error of one which is three is gonna be dq'd right it is gonna be removed even this is removed when i say remove it can be made zero programmatically and then we are saying front plus plus so now front will be f equals to two right this is what it would be pointing so if you perform one more dq operation what will happen is here of course it is not empty because f and r are 2 and 2 but now else if operation is going to be executed because front is equal to rear both are storing value 2 that is the second index location and what we will do is we will say x equals to error of front and now we are going to make front and rear equal to minus 1 so r will equal to be minus 1 f will become minus 1 so this is that minus 1 location the invalid location that we have assigned as the empty condition right so this is what we are doing over here because after moving this 2 from the queue we are left with no values which means that the queue is again become empty so we can again start nqueuing values right so here's where else if is going to be executed so this is the nq and dq operation when it comes to a simple q data structure now there is one drawback of this simple q data structure is because whenever you nq you keep on incrementing the rear so you go r plus plus r plus plus R++ okay and when you dequeue you keep on saying F++ also right so values go in like this 5 2 1 6 okay and when they are removed they are removed from this end and there comes a point where the leftmost values are unused these values go unused because the rear pointer and front pointer are always incremented in this way that is in the opposite way through which the values are inserted So that problem can be solved when we actually use circular queue and we'll discuss circular queue in some other video but I'm just trying to say that there are multiple ways in which queue data structure can be implemented and there are different types also.
So yeah these were the basic implementations of queue data structure and the standard operations that that are isEmpty, isFull, enqueue and dequeue. There is one more that is count we will directly see it in program because that is very basic. You simply take the difference between the rear and the front value and you add one to it and that will give you the count okay so that's that's just the basic thing now one last thing that is left out is the application so let's quickly go through that so since this queue data structure acts as a actual queue which is first in first out order. It is pretty much used for a lot of things like CPU scheduling wherein the processes come in a particular order and they have to be executed in that particular order so a queue data structure can be used.
Then we have disk scheduling, we have handling of interrupts in real time. So interrupt is a important signal which is used in operating systems to indicate a particular important operation and what happens is these interrupts are handled in the same order as they arrive which is first come first serve. So that's why first in first out data structure helps a lot. Also in real life, we can compare this to a call center phone system wherein queues will be used.
So if you are calling first and I'm calling second, obviously you will be served first and I will be served second, right? So if there are 10 people, there would be a particular queue which would be implemented in which the calls will be attended, right? And then use cases where the transfer of data is asynchronous. A lot of time queues are used for synchronization.
There are many more use cases, but these are some basic ones. which resemble the real world operations where Q data structures are used. Okay, so that's it for this video guys.
I hope you have a very good idea about what exactly is a Q data structure? How does it look like? What are the different standard operations? And we also saw the different algorithms which are used in implementing those Q data structure operations.
In the next video, we will actually implement those standard operations using C++ programming. So if you haven't yet subscribed, make sure you subscribe to this channel so that you get notified whenever I upload that video. and many other more videos on information technology. So thanks for watching, see you guys in the next video. Peace!