Understanding Queues in Data Structures

In this video, we are going to talk about queues in data structure. See, what is a data structure? It is a way of storing and organizing the data, right? We have discussed few data structures like arrays, linked list and stacks. In this video, we will see what is queue. So, queue is what? It is a linear data structure, you can say. Or you can say queue is an abstract data type. In this video, we will discuss queue as an abstract data type. ADT means when I say ADT it means we are going to define we are going to see the features or operations of queue. We will not go in detailed implementation. Right. See we can implement queues using arrays. linked list as well as using stack that implementation we will discuss in next video in this video we will see what is queue and what are different operations performed on queue fundamental operations fine as well as we will see some applications of queues so let us understand this concept with the real life scenario first of all right let us suppose there is a ticket counter fine it's a movie ticket counter you can consider right and now there is no one there in the queue or in the line fine first of all suppose you go and you stand there and after that second third fourth fifth five persons are there so obviously you if you are the first then you will get the ticket first Then you will go after that second person then third and fourth and then fifth and suppose before you there are five persons and after that you reach there. So you have you will have to stand at sixth position right and you will get ticket after the after you know these five persons fine so here the simple funda is what first in first out or you can say first come first serve the person who is for first in the row will get the ticket first, right? So now in the queue, this funda is known as first in, first out, FIFO. So queue is basically what? It is a structure, you can say it is an ordered list. As stack we have discussed, stack is an ordered list that follow the principle of LIFO, last in, first out. Queue is in collection or queue is an ordered list which follow what principle? First in, first out. right now what is that principle see you can say q is a structure that is going to follow some restrictions on insertion and deletion operation fine or that is going to follow a rule that is going to follow a principle and what is that rule insertion and deletion In case of Q, insertion would be performed from one end, right? And the name of that end, that end is known as rear or tail, right? And deletion would be performed from another end and that end is known as head or you can say front. Right? In Q, if you say more technically, then we will use rear and front, not head and tail. And rather than insertion, insertion means adding a data in the Q. Fine? So, the technical name in the context of Q, it is known as NQ. Right? And deletion is known as DQ. fine and in stack this insertion and deletion is known as push and pop fine So, NQ operations would be performed from one end and DQ operation would be performed from another end, right. So, we will see the logical representation of Q. If you logically represent the Q, it means it will have two ends, two open end, right. In stack, we have only one end, one open end, right. And Q would be represented something like this. It is having two end. One is this, one is this. Right? Suppose I am taking this end is rear. Right? And this is what? Front. Obviously, when you are going to implement this queue, you will have to take front and rear two variables. Right. That is must. So, insertion or you can see NQ operation would be performed from rear. From here, we can insert data in the queue. And if you want to delete data from the queue. it means from the front we can dequeue, we can delete data. right so this is what logical representation of a q fine suppose in q i have right now two elements two and three at some point of time right so at that time this front variable would be pointing to here and the rear variable would be pointing to here right and the index is suppose 0 and 1 now At some point of time, suppose we are implementing this queue using array and at some point of time we have only two elements in that queue and index is 0 and 1. So, front is 0 and rear is 1. Now, in this case if you want to insert. insert third element from where we can insert from this end only so what you need to do if suppose the size of this queue we have taken five we can insert five element the capacity is five right so now first of all you will increment this rear right so now rear plus plus that is rear would be pointing to this node and now you can insert another data suppose I have inserted five right and if you want to delete then from here only you can delete right so first in first out firstly we have inserted two and that is the first element you can delete if suppose you want to delete this five you cannot directly delete this five first of all you will have to delete this two from the queue then three from the queue after that only you can delete this five Right. So it is that is why it is known as it will follow FIFO principle. First in first out or you can say last in last out. Last in last out. Somewhere it is also written like this. That is same thing. Last integer that is enqueued in this queue is 5 and that would be the last element you can remove. So, last in last out this is queue. So, now we will see some operation that can be performed on a. queue so you can define queue as it is a ordered list or you can say it is a collection in which insertion can be performed from one end that is from rear end and deletion can be performed from another end that is from front end of the queue fine and it is going to follow it is a structure you can say that is going to follow the fifo rules that is first in first out right so now we will see some operation that can be performed on q so two operations we have discussed that is first is NQ and that is second is DQ right these are two fundamental operations NQ and DQ NQ means inserting or adding a data in the queue DQ means deleting a data from the queue see here in NQ I am passing 2 as an argument because I want to suppose I want to insert 2 in the queue then I can pass this in the NQ in DQ no need to pass anything because always that element would be DQ'd from the front so the element which is at the front index of the queue that would be deleted right so no need to pass anything third may be front or you can say peak In stack it was top. It means the motto of this operation is what? It is going to tell you what is the element at the front of the queue. Right? We will see what is the element at the front of the queue without removing that element from the queue or without dequeuing that element from the queue. Right? Now, is queue full? you can check by is full function it is it will return true if the q is full it will otherwise it will return false is empty same we have discussed in stack if the q is empty then it would return true otherwise it would return false right now see the logical representation of q so this is the logical representation of q fine any end you can take front or rear but you have to take care of that thing deletion from front and insertion from rear right so here i am taking this is what front and this is what rear I will insert always from here delete from here you can take front this side rear this side as you wish but insertion and deletion would be according to the rule only fine now if you want to insert some data here obviously you need to specify the size of this queue suppose the capacity of queue is 5 you can say size I am taking is 5 how we will take the size 5 how we will implement this queue that thing we will discuss in next video so it means i can insert five element in this queue right here i have this end and index is 0 1 2 3 and 4 so initially there is nothing in the queue right in that case what we will do both friends front end this rear would point to minus 1. Hypothetically we assume that there is a minus 1 index and these are pointing to minus 1. It means q is empty right that is the signal. If this is minus 1 it means q is empty. Now I want to enqueue 2. Now what would happen? See. Front is minus 1, rear is also minus 1. Obviously, we will increase front and rear both. So, front plus plus and rear plus plus also. Right. So, now front is also pointing to here and at this point of time rear is also pointing to here. at 0 and now we can insert here 2 right now suppose again i want to nq 3 i have called again function nq and suppose 10 i want to insert in that case what will happen see Front will always point to this node, the front one, the front element. We will not move this front for inserting the data. Inserting would be always from the rear part. So the rear. variable we are going to move so first of all we will increase the rear rear plus plus means now rear is pointing to here and now here i can insert 10 again suppose i am calling nq minus 1 again what we will not touch this front we will move this rear insertion from rear only that thing you have to take care rear plus plus means rear would point here and now here i can insert minus 1 see at this point of time front is 0 and rear is now 2 right now suppose I am calling DQ function no need to pass anything because always the data would be deleted from front now we you can touch this front now we will not touch this rear in DQ we will touch this front right so now suppose you want to print the data you have DQ so you can write down printf the data you have DQ is from the queue you can print this value and after that what you will do you will do front plus plus right so now front is pointing to here front is one rear is two or in dq simply you will write front plus plus that is also fine because now this is not a part of q the part of q is only two elements whatever between front and rear that is part of q this is now a garbage value and we don't care what garbage value lies here in future future if you will access this cell and if you will write here something then this value would be overwritten that is fine fine now suppose I am calling nq function three times so now nq 0 means from rear I will not touch this front from rear and rear only I can insert rear plus plus rear would be pointing to here and here I can insert 0 nq 1 rear plus plus here I can insert 1 nq 5 then rear plus plus but what we have the size till here only so if rear is what rear is equal to 4 it means rear is equal to this maximum size minus 1 index is 4 now maximum size is 5 in that case you will print we cannot insert any data it means you can say overflow condition this is overflow condition right so this would print what overflow condition this is now overflow condition right and what is underflow condition suppose you want to dq and there is nothing in this list right both front and rear are minus 1 in that case what that is an underflow condition that is q is empty right now suppose before calling this dq function i am calling peak function after this nq or you can say front so it will return what front value is now 10 because see q is between from front to rear that is here to here this is what garbage value so i'll rub this one this is garbage base value right so now this will return 10 after that suppose you are calling dq function continuously three times what would happen first of all dq it means front plus plus front would point here again dq front plus plus again dq front plus plus right means front and rear both are pointing to here now this is what a garbage value this is not a q suppose i am removing these value from here from these cell because we can override these values right now as you can see both front Front and rear are pointing to head. Here both are at same index. So, in DQ you can write down one condition you can check that condition also if front and rear is equal if front is equal to is equal to rear in that case what it means only one element is there in the queue. So, what you can do after. moving this what will what would happen front and rear is equal to minus one you can set front and rear is equal to minus one because this is the condition we have set for mptq right or if you will not do this thing then simply same processor front front plus plus right front plus plus means front would point to here that is 5 front becomes 5 so another condition of checking the empty queue is what if front is greater than this rear because rear is still 4 front is 5 right in that case it means queue is empty front plus plus means we have deleted this queue right so deleted this element from the queue so it means queue is empty so when front becomes greater than rear then also it is empty So, we are going to see how to write down these condition in next video. Fine. Now, suppose if you talk about the time complexity, then in that case, these operations would take order of 1 only. Because we are not going to write any loops or anything for performing these operations. So, it would take order of 1 only. Right. Constant time. Now, suppose at some point of time, both front and rear are pointing to this node. It means Q is having only one data. This, this, this, this. These four cells. are empty right and now if you call nq in that case it would return what q is full that is the drawback why it will return q is full because see see here rear is what pointing to 4 rear is 4 that is maximum size minus 1 and that is condition of what overflow condition means the q is full now it will show you q is full right but see these spaces are free but we cannot insert here this is wastage of the space so this is drawback of this queue we have a solution of this queue that is the circular queue that also we will discuss later fine so but this is now a drawback you have space but you cannot insert here data right now we will see some applications of queue so the most common application of this queue data structure is what it is used where you want to you know serve the request on a single shared resource suppose you have a single resource and that is shareable let us take you you can take an example of printer suppose you have one printer and that is shareable fine so what would happen it's not like that suppose there are five pcs and these five pcs are sharing one printer it's not like that it will give command and this will print and at the same time it will print it will give command and it will print right what the sprinter will do suppose this this has given some command to printer data and now the printer is printing now at the same time computer this three it has given command to this printer then what would happen the printer is busy now so what printer will do it will obviously it will have a program so that request would be stored in queue after that suppose this printer would give the request so it would store here after that this this would store here so it will in the memory in the printer memory it will what make a queue of all the request right first of all it will print whatever the request it has given then it will fulfill request of three then two like this right and queues are also used in real life scenario like you can take an example of when you call in customer care then sometimes they tell you that they tell you to hold on for few minutes because their representative is not free so what they do they use queues to put the people on hold right until their representative are free Next you can take an example of processor. See you have only one processor, CPU you can see. So the processors would be placed in queue. In operating system I guess we have discussed many times when we were discussing the concept of operating system. Then you can check out in the playlist. There are ready queue, there are waiting queue. So the processors would be put in the queue and as soon as processor gets free. free it will take from the queue it will take the processes from the queue one by one right. So all the processes are also put in the queue right because processor is what it is a shareable resource any process all the processes can share this processor right but obviously we cannot execute all the processes at the same time. So you have to put those processes in waiting or you can say those processes are put in queues right. So, these are some example, these are some applications of queue data structure and there are many more applications of queue, we will discuss all these one by one in later videos. So, in next video basically we will discuss how to implement queue using arrays and then using linked list and then using stacks fine. So, I will see you in the next video till then bye bye take care.

So, queue is what? It is a linear data structure, you can say. Or you can say queue is an abstract data type.

In this video, we will discuss queue as an abstract data type. ADT means when I say ADT it means we are going to define we are going to see the features or operations of queue. We will not go in detailed implementation.

Right. See we can implement queues using arrays. linked list as well as using stack that implementation we will discuss in next video in this video we will see what is queue and what are different operations performed on queue fundamental operations fine as well as we will see some applications of queues so let us understand this concept with the real life scenario first of all right let us suppose there is a ticket counter fine it's a movie ticket counter you can consider right and now there is no one there in the queue or in the line fine first of all suppose you go and you stand there and after that second third fourth fifth five persons are there so obviously you if you are the first then you will get the ticket first Then you will go after that second person then third and fourth and then fifth and suppose before you there are five persons and after that you reach there.

So you have you will have to stand at sixth position right and you will get ticket after the after you know these five persons fine so here the simple funda is what first in first out or you can say first come first serve the person who is for first in the row will get the ticket first, right? So now in the queue, this funda is known as first in, first out, FIFO. So queue is basically what? It is a structure, you can say it is an ordered list.

As stack we have discussed, stack is an ordered list that follow the principle of LIFO, last in, first out. Queue is in collection or queue is an ordered list which follow what principle? First in, first out. right now what is that principle see you can say q is a structure that is going to follow some restrictions on insertion and deletion operation fine or that is going to follow a rule that is going to follow a principle and what is that rule insertion and deletion In case of Q, insertion would be performed from one end, right? And the name of that end, that end is known as rear or tail, right?

And deletion would be performed from another end and that end is known as head or you can say front. Right? In Q, if you say more technically, then we will use rear and front, not head and tail. And rather than insertion, insertion means adding a data in the Q. Fine?

So, the technical name in the context of Q, it is known as NQ. Right? And deletion is known as DQ.

fine and in stack this insertion and deletion is known as push and pop fine So, NQ operations would be performed from one end and DQ operation would be performed from another end, right. So, we will see the logical representation of Q. If you logically represent the Q, it means it will have two ends, two open end, right. In stack, we have only one end, one open end, right.

And Q would be represented something like this. It is having two end. One is this, one is this.

Right? Suppose I am taking this end is rear. Right? And this is what? Front.

Obviously, when you are going to implement this queue, you will have to take front and rear two variables. Right. That is must. So, insertion or you can see NQ operation would be performed from rear.

From here, we can insert data in the queue. And if you want to delete data from the queue. it means from the front we can dequeue, we can delete data. right so this is what logical representation of a q fine suppose in q i have right now two elements two and three at some point of time right so at that time this front variable would be pointing to here and the rear variable would be pointing to here right and the index is suppose 0 and 1 now At some point of time, suppose we are implementing this queue using array and at some point of time we have only two elements in that queue and index is 0 and 1. So, front is 0 and rear is 1. Now, in this case if you want to insert.

insert third element from where we can insert from this end only so what you need to do if suppose the size of this queue we have taken five we can insert five element the capacity is five right so now first of all you will increment this rear right so now rear plus plus that is rear would be pointing to this node and now you can insert another data suppose I have inserted five right and if you want to delete then from here only you can delete right so first in first out firstly we have inserted two and that is the first element you can delete if suppose you want to delete this five you cannot directly delete this five first of all you will have to delete this two from the queue then three from the queue after that only you can delete this five Right. So it is that is why it is known as it will follow FIFO principle. First in first out or you can say last in last out. Last in last out. Somewhere it is also written like this.

That is same thing. Last integer that is enqueued in this queue is 5 and that would be the last element you can remove. So, last in last out this is queue.

So, now we will see some operation that can be performed on a. queue so you can define queue as it is a ordered list or you can say it is a collection in which insertion can be performed from one end that is from rear end and deletion can be performed from another end that is from front end of the queue fine and it is going to follow it is a structure you can say that is going to follow the fifo rules that is first in first out right so now we will see some operation that can be performed on q so two operations we have discussed that is first is NQ and that is second is DQ right these are two fundamental operations NQ and DQ NQ means inserting or adding a data in the queue DQ means deleting a data from the queue see here in NQ I am passing 2 as an argument because I want to suppose I want to insert 2 in the queue then I can pass this in the NQ in DQ no need to pass anything because always that element would be DQ'd from the front so the element which is at the front index of the queue that would be deleted right so no need to pass anything third may be front or you can say peak In stack it was top. It means the motto of this operation is what?

It is going to tell you what is the element at the front of the queue. Right? We will see what is the element at the front of the queue without removing that element from the queue or without dequeuing that element from the queue.

Right? Now, is queue full? you can check by is full function it is it will return true if the q is full it will otherwise it will return false is empty same we have discussed in stack if the q is empty then it would return true otherwise it would return false right now see the logical representation of q so this is the logical representation of q fine any end you can take front or rear but you have to take care of that thing deletion from front and insertion from rear right so here i am taking this is what front and this is what rear I will insert always from here delete from here you can take front this side rear this side as you wish but insertion and deletion would be according to the rule only fine now if you want to insert some data here obviously you need to specify the size of this queue suppose the capacity of queue is 5 you can say size I am taking is 5 how we will take the size 5 how we will implement this queue that thing we will discuss in next video so it means i can insert five element in this queue right here i have this end and index is 0 1 2 3 and 4 so initially there is nothing in the queue right in that case what we will do both friends front end this rear would point to minus 1. Hypothetically we assume that there is a minus 1 index and these are pointing to minus 1. It means q is empty right that is the signal. If this is minus 1 it means q is empty. Now I want to enqueue 2. Now what would happen?

See. Front is minus 1, rear is also minus 1. Obviously, we will increase front and rear both. So, front plus plus and rear plus plus also.

Right. So, now front is also pointing to here and at this point of time rear is also pointing to here. at 0 and now we can insert here 2 right now suppose again i want to nq 3 i have called again function nq and suppose 10 i want to insert in that case what will happen see Front will always point to this node, the front one, the front element.

We will not move this front for inserting the data. Inserting would be always from the rear part. So the rear. variable we are going to move so first of all we will increase the rear rear plus plus means now rear is pointing to here and now here i can insert 10 again suppose i am calling nq minus 1 again what we will not touch this front we will move this rear insertion from rear only that thing you have to take care rear plus plus means rear would point here and now here i can insert minus 1 see at this point of time front is 0 and rear is now 2 right now suppose I am calling DQ function no need to pass anything because always the data would be deleted from front now we you can touch this front now we will not touch this rear in DQ we will touch this front right so now suppose you want to print the data you have DQ so you can write down printf the data you have DQ is from the queue you can print this value and after that what you will do you will do front plus plus right so now front is pointing to here front is one rear is two or in dq simply you will write front plus plus that is also fine because now this is not a part of q the part of q is only two elements whatever between front and rear that is part of q this is now a garbage value and we don't care what garbage value lies here in future future if you will access this cell and if you will write here something then this value would be overwritten that is fine fine now suppose I am calling nq function three times so now nq 0 means from rear I will not touch this front from rear and rear only I can insert rear plus plus rear would be pointing to here and here I can insert 0 nq 1 rear plus plus here I can insert 1 nq 5 then rear plus plus but what we have the size till here only so if rear is what rear is equal to 4 it means rear is equal to this maximum size minus 1 index is 4 now maximum size is 5 in that case you will print we cannot insert any data it means you can say overflow condition this is overflow condition right so this would print what overflow condition this is now overflow condition right and what is underflow condition suppose you want to dq and there is nothing in this list right both front and rear are minus 1 in that case what that is an underflow condition that is q is empty right now suppose before calling this dq function i am calling peak function after this nq or you can say front so it will return what front value is now 10 because see q is between from front to rear that is here to here this is what garbage value so i'll rub this one this is garbage base value right so now this will return 10 after that suppose you are calling dq function continuously three times what would happen first of all dq it means front plus plus front would point here again dq front plus plus again dq front plus plus right means front and rear both are pointing to here now this is what a garbage value this is not a q suppose i am removing these value from here from these cell because we can override these values right now as you can see both front Front and rear are pointing to head. Here both are at same index.

So, in DQ you can write down one condition you can check that condition also if front and rear is equal if front is equal to is equal to rear in that case what it means only one element is there in the queue. So, what you can do after. moving this what will what would happen front and rear is equal to minus one you can set front and rear is equal to minus one because this is the condition we have set for mptq right or if you will not do this thing then simply same processor front front plus plus right front plus plus means front would point to here that is 5 front becomes 5 so another condition of checking the empty queue is what if front is greater than this rear because rear is still 4 front is 5 right in that case it means queue is empty front plus plus means we have deleted this queue right so deleted this element from the queue so it means queue is empty so when front becomes greater than rear then also it is empty So, we are going to see how to write down these condition in next video. Fine. Now, suppose if you talk about the time complexity, then in that case, these operations would take order of 1 only.

Because we are not going to write any loops or anything for performing these operations. So, it would take order of 1 only. Right.

Constant time. Now, suppose at some point of time, both front and rear are pointing to this node. It means Q is having only one data.

This, this, this, this. These four cells. are empty right and now if you call nq in that case it would return what q is full that is the drawback why it will return q is full because see see here rear is what pointing to 4 rear is 4 that is maximum size minus 1 and that is condition of what overflow condition means the q is full now it will show you q is full right but see these spaces are free but we cannot insert here this is wastage of the space so this is drawback of this queue we have a solution of this queue that is the circular queue that also we will discuss later fine so but this is now a drawback you have space but you cannot insert here data right now we will see some applications of queue so the most common application of this queue data structure is what it is used where you want to you know serve the request on a single shared resource suppose you have a single resource and that is shareable let us take you you can take an example of printer suppose you have one printer and that is shareable fine so what would happen it's not like that suppose there are five pcs and these five pcs are sharing one printer it's not like that it will give command and this will print and at the same time it will print it will give command and it will print right what the sprinter will do suppose this this has given some command to printer data and now the printer is printing now at the same time computer this three it has given command to this printer then what would happen the printer is busy now so what printer will do it will obviously it will have a program so that request would be stored in queue after that suppose this printer would give the request so it would store here after that this this would store here so it will in the memory in the printer memory it will what make a queue of all the request right first of all it will print whatever the request it has given then it will fulfill request of three then two like this right and queues are also used in real life scenario like you can take an example of when you call in customer care then sometimes they tell you that they tell you to hold on for few minutes because their representative is not free so what they do they use queues to put the people on hold right until their representative are free Next you can take an example of processor. See you have only one processor, CPU you can see.

So the processors would be placed in queue. In operating system I guess we have discussed many times when we were discussing the concept of operating system. Then you can check out in the playlist.

There are ready queue, there are waiting queue. So the processors would be put in the queue and as soon as processor gets free. free it will take from the queue it will take the processes from the queue one by one right.

So all the processes are also put in the queue right because processor is what it is a shareable resource any process all the processes can share this processor right but obviously we cannot execute all the processes at the same time. So you have to put those processes in waiting or you can say those processes are put in queues right. So, these are some example, these are some applications of queue data structure and there are many more applications of queue, we will discuss all these one by one in later videos. So, in next video basically we will discuss how to implement queue using arrays and then using linked list and then using stacks fine.

So, I will see you in the next video till then bye bye take care.

Transcript for:Understanding Queues in Data Structures

Transcript for:
Understanding Queues in Data Structures