4.7 Deque in data structure | introduction to deque - Double Ended Queue

in this lecture we are going to talk about DQ that is double ended queue right we will discuss what is DQ how this is different from the q''-word you can say linear to and circular queue fine as well as we will see some types you can say two types of this DQ and some applications of BQ right and how we can implement this Q in memory right see I have already discussed about Q and circular Q's fine with their operations plus implementation I'll provide you the link of that playlist in the Seibert and as well as in the description box you can check out there we are left with D Q that is double ended queue and priority queues right so in this video we'll discuss about a double ended queues sometimes it is also known as Dec fine now see I guess you remember what is a queue it is a list where you can say insertion would be from one end and deletion would be from another end right see this is how we are going to represent a queue so insertion would be from one end and that end is known as rear end of the queue and deletion would be from another end that is known as known as front of the queue you can take here front here rear but you you should follow the rules if you take here rear end this rear end you consider this and is the rear and then insertion will be from here and deletion will be from here that is the destruction in the queue now as the names has a straight double ended queue in this case how this is different from this cube insertion and deletion are allowed from both the ends right to make it you can say BQ what you need to do from here see this is what a deletion so here you can insert from here you can insert and delete from here also you can insert and delete right so insertion and deletion are allowed from both the ends it is known as double ended queue right so if you define there you can say it is a linear list in which insertion and deletion or you can say into and DQ operations are allowed from both ends alright so it is you can say a generalized version of Q so here also you can consider this as front this has rear as you visual this has front this has real because insertion and deletion are allows from both things right so now you can also write down some properties of this Q see it is having the properties of both strap and Q see stack is going to follow a leaf or property and Q is going to follow FIFO property this we know already we have already discussed so see it supports the properties of both stack and queue right so it can be used as both stack and queue sometimes you can use that it as a stack and queue if you are using it as a stack then what you need to take care in in this case last in first out property it should fall over last in first out property to make it has a step right it means something like this here from here only I can insert and from here only you can delete right this is one end of the queue implement insertion and deletion from this end only you will not touch this end it means this is what Stagner horizontally if you will represent it something like this right this is the one end from where you can insert and from here also you can delete and to use it as a cue what you need to take care in the queue we know that from it insertion can be from one end you can say from this and deletion will be from this end so you can implement this thing using this DQ also right insertion you can put some destruction here and you can use it as a queue because it is going to follow with the property of both stack and queue fine now types of take you see basically two types of DQ are there one is input restricted and second one is output restricted right an input restricted q what is the case see as the name suggests input restricted means you are going to put some restrictions on input on you can say insertion but you can say on NQ operation right so here in this case and this DQ insertion can be allowed only from one end deletion is allowed from both ends right so how we are going to represent this queue that input restricted queue see if suppose I'm taking this as a queue fine so this is front this is real so insertion can be from one end only either from this or this as we wish from where you are one two from which and you want the insertion suppose I want insertion from here right insertion can be from this end only you can delete from here you can delete from here all right we are going to put in strong restriction only on the input operation this is what input restricted queue now next is output restricted queue it means as the name suggests you are going to put restrictions on output or you can say that delete operation it means a deletion can be possible from one end insertion is possible from both ends right so suppose this is a queue this is front this is rear and here also you can take either end at which you can perform deletion but you should take care of this thing that deletion can be from that end right suppose I am taking deletion from this end so you cannot delete from the same you can insert from this end you can insert from this end right so this is what output restricted DQ this is input restricted DQ these are two types of DQ you can say now next is what type of operations you can perform on a DQ see basically these four types of operations you can perform you can insert that front delete from front insert atrial delete from rear right how we are going to implement these operations that thing we will discuss in the next video right now other than these operations what you can do you can perform what see in the q''-word operation we can perform other than insertion and deletion or you can see other than in 22 peek means we are going to get the front element so here you can say you can get the front element as well as the rear element so you can say get front get ring here fine oh you can say front and rear means you want to check out which value is at the front of the queue which value is at the rear of the queue and other than these two operations are also there that is is full and is empty right this operation is going to return true if the DQ is full otherwise Falls and SMPT means this is going to return true if the DQ is empty otherwise it is going to return false how we will implement these operations on a DQ that we will discuss in the next video with proper code so now next thing is memory representation of this DT or you can say how we are going to implement this DQ how we are which data structure you are going to use to implement this beacon so the answer is either you can use a circular array or you can use a doubly-linked list right how we will implement this using circular array that thing we will discuss in the next video what a circular array see we have already discussed the circular queue implementation in that case we have discussed that we can implement that circular queue using a circular arrays right so now in that case what is the case here suppose we have front and rear so now the situation is something like this here I have 3 4 & 2 and this is free now so front is pointing to here and rear is pointing to here now I want to perform this insert at rear insert adrià here but now see suppose array size is 4 only right so now you cannot do rear plus plus means here you cannot insert but it should not return that q is full why so because we are using circular array concept something like this logically you can represent it something like this is a circular adding zero one two and three after this three index we will move to the 0th index means something like this and this space is free so you can insert here this is what a circular array concept so you can implement this DQ using circular adding or you can implement it using linked list also doubly linked list also and here in this case all the operations that is insertion and deletion should take what order of one time complexity right now we will see some applications of DQ C as we have discussed it has the property of both stack and queue right so we can use it as stack and queue both fine so the applications of stack and queue would be obviously the application of this DQ so first application is you can say it can be used to perform the redo and undo operations my second thing you can say it that you can also be used as a palindrome checker palindrome means if you read a string from the front and if you read from the and then it would be same from both things fine suppose you can take an example of this thing if you read from here then radar and if you read it from the end then also it would be rather so it can also be use as a palindrome checker now the very important application is what it is used in what multi processor scheduling see what is that thing it means multi processor means you can say how multiple processors are there suppose we are taking two processors and each processor is assigned some job and every or you can say process and every process is having multiple threads right so each processor is containing its key word you can say a DQ this is also maintaining its DQ this is also maintaining its dake you see these beacuse are used to maintain those threads which are ready to execute now see here when a process creates a new process suppose the process is a process this processor is executing a process so a process can you can say produce its trial process so that process would be inserted at the front of this DQ but suppose this processor has executed its all the threads right now this processor this processor will steal a thread from this processor or you can say the process of this processor but this will take a thread from the rear right from rear of this DQ and after stealing this thread it will execute the thread on this processor means on its own and it will add this thread to its friend and this processor will take you can say threads from its front so here you can say this we can delete from the rear and we can delete from the front we can insert from both the ends also and delete from both ends so here too to implement this thing in this multiprocessor scheduling algorithm DQ is going to be used right so this complete process is known as what it is known as known as a stream algorithm for job scheduling say this is just a brief overview of what a steal algorithm is there if you want me to make a video on this thing you can write down me in the comment box right see there can be many more applications of this DQ other than these three that we have discussed here fine but I guess this is fine for the introduction of DQ in next video we will discuss how to implement double ended queue using circular arrays right so I will see in the next video does number by a taking

Channel: Jenny's lectures CS/IT NET&JRF

Views: 122,222

Keywords: data structure tutorials, operating system, data structure and algorithms, what is deque in data structure, dequeue in data structure, double ended queues in data structure, deque and its types, deque in data structure program using array, jenny data structures, jennys lecture, jenny's lectures cs/it NET&JRF, ugc net computer science tutorials, gate cs lectures, jayanti khatri lamba, cs it youtube channels, data structure notes, queue in data structure, what is circular queue

Id: pqg0SOPRlJ4

Length: 12min 44sec (764 seconds)

Published: Fri Oct 18 2019