4.1 Queue in Data Structure | Introduction to Queue | Data Structures Tutorials

in this video we are going to talk about queues in data structure see what is the data structure it is a way of storing and organizing the data right we have discussed few data structures like arrays linked lists and stacks in this video we will see what is U so Q is what it is a linear data structure you can see or you can say Q is an abstract data type in this video we will discuss Q as an abstract data type ADT means when I say edit E it means we are going to define we are going to see the features or operations of Q we will not go in detail implementation right see we can implement Q's using arrays linked lists as well as using stack that implementation we will discuss in next video in this video we will see what is Q and what are different operations performed on Q fundamental operations fine as well as we will see some applications of Q's so let us understand this concept with a real-life scenario first of all right let us suppose there is a ticket counter fine that'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 be 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 so the person who is 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 Q is basically what it is a structure it is an ordered list as stack we have discussed staff is an ordered list that follow the principle of Li for last in first out queue is an 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 queue insertion would be performed from one end right and the name of that and that end is known as rear or till right and deletion would be performed from another end and that end is known as head or you can say friend right in queue if you say more technically then we will use a rear end front not head and pain and rather than insertion insertion means adding a data in the queue fine so the technical name in the for in in this in the context of queue it is known as in queue right and deletion is known as DQ by and in stab this insertion and deletion is not known as push and pop fine so NQ operation should be performed from one end and DQ operation would be performed from another end right so we will see the logical representation of queue if you logically represent the queue it means it will have two ends to open it right in stab we have only one end one opponent like and queue would be represented something like this it is having two and one is this one is this right suppose I am taking this end is rear right and this is what friend obviously when you are going to implement this cue you will have to take front and rear two variables like that is must so insertion or you can see NQ operation would be performed from rear from here we can insert data in the cube and if you want to delete data from the queue it means from the front we can DQ we can delete data right so this is what a logical representation of a queue fine suppose and queue 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 zero and one at some point of time we are suppose we are implementing the skew using array and at some point of point of time p.m. only two elements in that queue and index is zero and one so front is zero and rear is one now in this case if you want to insert third element from where we can insert from this end only so what you need to do if suppose the size of this do 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 real would be pointing to this node and now you can insert another it 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 later this five you cannot directly delete this five first of all you will have to delete this two from the queue then three from that you after that only you can delete this 5 right so it is that is why it is no it is known as it will follow FIFO principal love first-in first-out or you can say last in last out last in last out somewhere it is also written like this that the same thing last integer that is in queued in this 2 is 5 and that would be the last element you can remove so last in last out this is Q so now we will see some operation that can be performed on a Q so you can define Q 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 a 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 operation we have discussed that is first is n 2 and that is the second is DQ right these are two fundamental operations and Q and D Q n 2 means inserting or adding a data in the q DQ ms deleting a data from the queue see here in NQ I'm passing to 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 the 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 friend or you can say peek in stack it was top it means the motto of this operator operation is what it is going to tell you what does 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 from the queue or without deterring 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 queue is full it will otherwise it will return phones is empty same we have discussed in stack if the queue is empty then it could return true otherwise it will return false right now see the logical representation of you so this is the logical representation of queue 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 fine you can say size I am taking is 5 how will take the size 5 Huggle implement this through that thing we will discuss in next video so it means I can insert 5 element in this queue right here I have 3 this end and index is 0 1 2 3 & 4 so initially there is nothing in the queue right in that case what we will do both friend 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 queue is empty right that is the signal if this is minus 1 it means Q is impeding now I want to include 2 now what would happen see friend 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 the zero and now we can insert here too right now suppose again I want to NQ three I have hold again function and Q and suppose ten I want to insert in that case what will happen see friend 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 real variable we are going to move so first of all you will increase the rear rear plus plus means now rear is pointing to here and now here I can insert ten again suppose I am calling NQ minus 1 again what we will not touch this front we will move this rear insertion from drear only that thing you have to take care rear plus plus means rear would point here and now here I can insert minus 1 say at this point of time front is 0 and rear is now - right now suppose I am calling DQ function no need to pass anything because always the data would be deleted from front now when you can touch this front now we will not touch this rear in DQ we will touch this friend right so now suppose you want to print the data you have DQ'd so you can write down printf the data you have DQ'd 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 queue the part of queue is only two elements whatever between front and rear that is part of you this is now a garbage value and we don't care what the garbage value lies here in future if you will access this selling and usually if you will write here something that this value would be overwritten that is fine fine now suppose I am calling NQ function 3 times so now NQ 0 means from rerai I will know touch this front from rear I'm where only I can insert a year plus plus a year would be pointing to here and here I can insert a 0 into one rear plus plus here I can insert one into five then rear plus plus but what we have the size till here only so if rear is what rear is equal to four it means rear is equal to this maximum size minus one index is 4 now maximum size is five in that case you will print we cannot insert any data you means you can say all flow condition this is all flow condition right so this will print what overflow condition this is an hour of overflow condition right and what is under flow condition suppose you want to DQ and there is nothing in this list right both front and rear are minus one in that case what that is done under flow condition that is to is empathy right now suppose before calling this DQ function I am calling peak function after this NQ but you can say front so it will return what front value is now n because C Q is between from front to rear that is here to here this is what garbage value so I rub this one this is garbage 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 foot point here again DQ front plus plus AG + 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 cure suppose I am removing these value from here from these cell because you can have override these values right now as you can see both front and rear are pointing to hair both are at same index so in de you can write down one condition you can check that condition also if front and rear is different is equal to is equal to read in that case what it means only one element is there in the queue so what you can do after removing this what will what would happen friend and driller is equal to minus one you can set front and rear is equal to minus one because this is the we have set for em ptq right or if we will not do this thing then simply same processor front plus plus right front plus plus means front foot point to here that is five friend becomes five so another condition of checking the in particular is what if front is greater than this rear because rear is still four front is five right in that case it means Q is empathy friend plus plus means we have deleted this Q right so delete this element from the queue so it means Q is empathy so when friend becomes greater than we are then also it is empathy 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 one only because we are not going to write any loops or anything for performing these operations so it would take order of one only right constraint time now suppose at some point of time both friend and Bria 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 near is what pointing to for or ear is for that is maximum size minus one and that is condition of what or flow 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 what wastage of the space so this is a drawback of this Q we have a solution of this cube that is the circular queue that also I 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 Q 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 shared 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 pieces 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 this printer will do suppose this this has given some command to print a date and now the printer is printing now at the same time computer this tree it has given command to this printer then what would happen the printer is busy 'no 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 requests right first of all it will print whatever the request it has even then it will fulfill requests of three then two like this right and queues are also used in real life scenario like you can take an example of a new oil in customer care then sometimes they tell you that they tell you to hold on for a 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 fine next you can take an example of processor see you have only one processor CPU you can see right so the processes 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 fine so the processes would be put in the queue and as soon as processor gets 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 but obviously we cannot execute all the processes at the same time so you have to put those processes and 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 youth' 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 lists and then using stacks fine so I'll send the next video till then bye bye take care

Channel: Jenny's Lectures CS IT

Views: 561,410

Keywords: data structures tutorials, operating system, what is queue, queue in data structure in c, how to implement queue using array, introduction to queue in data structure, ugc net computer science preparation strategy, jenny's lectures, jenny data structures, jenny's lectures CS\IT NET&JRF, GATE computer science, c programming, queue operations in data structure, queue using linked list, ds notes, dsa tutorial, data structures and algorithms, stacks and queues in data structure

Id: zp6pBNbUB2U

Length: 20min 18sec (1218 seconds)

Published: Thu Sep 12 2019