Hello ji , how are you all? this is love Babbar And welcome to the channel Code help , we have reached lecture no-60 , here we are going to introduce a new topic Queue , we will learn many things , what is it? STl? Will implement it , it will be fun What is queue ? Stand in a line , that is your queue , here we are talking about DS Queue is a type of data structure which flows FIFO , in short I have this data structure Lets take a simple example , here is an ATM People come from here take money and go back from here This is out , this is in , there are 4 person Whoever goes inside 1st , will come out 1st , a queue works in that way this is a line , this is your ATM , whoever goes inside 1st , comes out 1st , we call it FIFO order The data structure which flows this order we call it queue This is a queue, push(1) inside queue You pushed 1 , then you said to push 5 , it pushed 5, 7, 8, 12 Then someone said to pop , which went inside 1st will come out 1st , so you removed 1 then 5, understood? when we were inserting like this But when we pop() , we keep in mind 1st in 1st out this is a queue , this is front , and rear representing this Whenever you push something , push->rear , pop->front , what do you mean by that ? push->1, 5 ,7 ,8, 12 , so I pushed 1 Now rear moved here , push 5 , then it moved here , then 7 then push 8 and moved here push 12 , then it moved here , now I say to pop() two times When I am doing this pop() , it will happen from the front , moved it ahead Again popped and moved front by one step At present this much elements have left , so you have understood all Whenever I push , it will be pushed at rear , when I pop it happens at front Lets 1st give shout out to our sponsors Coding Ninjas is the one of the largest coding education platform , where you can take different types of courses if you are interested in paid courses , want to do dev , machine learning , android , web dev, system design OS ,DBMS , DSA in Java , Python Then you can take the courses from here , the best thing is that here you get one on one doubt solving support If you have any doubt , then it will be resolved within 1-2 hours , courses are very well structured If you put the efforts then you will definitely get the result , educators have already cracked big companies , no need to worry It is available in both Hindi and English , you will get the hint videos while solving the questions If you want to buy any paid courses then link will be given in the description , from there you can get 20% maximum discount , thank you If I will have a queue , then there should be push() , through which I can push element There should be pop() , so that I can remove the element One size operation , so that I can know the size of queue isEmpty() , so that I can know whether it is empty or not As we saw in stack , there should also some operations If we take about STL , can I use STL here queue cpp reference , inside it there are some elements From here I can push If I talk about the declaration , I will create like this , queue<int> q I want to push -> q.push(17), I want to pop -> q.pop() If I have to find the size ->q.size () If I want to check empty ->q.empty(), it will return a bool front points to the 1st element and rear last I want to see which element is in front q.front() , I will get the 1st element If this is my queue , front is pointing here , and rear here , you see from here Here I shown you some methods , we want to see it by running Create a queue of int type q we have to include it here push some elements 11 ,15 ,13 cout<<"size of queue is " << q.size()<<endl; 3 , it is working properly , lets I said q.pop() I again put this statement Here it should give 2 now , before it was 3 now it is 2 We want to check whether it is empty or not I ran it , i know there are 2 elements , here it will give queue is not empty , I ran it If I pop() 3 times then it will give empty If I run now , size zero , queue is empty , When I pushed 11 , I want to see what is there in front I copied it here , answer will be same , because we have not pop anything else I ran it 1st in queue there was only 11 , so it was pointing to 11 Then we inserted 15 , again front is pointing to 11 , then 13 , still it is pointing to 11 ,so all answer should be 11 So we saw push , pop, size , empty , front Here I can see some more operations , read and try it We have basically covered important things , which you will use If you have to use queue STL , then you will not afraid , you know all of these Here I have seen the queue STL thing , now I have to implement queue Create class for queue , and implement it from scratch , there can be two types of implementations By using array and linked list I have shown you stack by using array , in queue also I am showing Implementing in linked list is for H/W We have understood how to insert in queue , remove , etc Lets say I have create a class , and implement everything from scratch What do you mean by enqueueu () , push() , insert() we are calling these enqueue() in same way dequeue(0 is pop() basically this is your push(0 and this is your pop() Now I if i have to implement class , then we know There will be front , it will represent the starting of queue , and rear , it will represent the ending Size , it will tell the total size , and this is your array If I have to make the class of queue , then I have to see the data members I need an array , the size of array , front and rear , check whether it is full or not In construction I should get the size , I have taken random size In starting this is your array This is your front , this is your rear , in short your queue is empty ,in starting front=0 ,rear=0 Now if I get a push operation , 1st i will check whether it is full or not If full , how will we know ? Whenever your rear reaches here , rear=n-1 empty condition will be , front==rear We will check whether it is full or not, lets move ahead else , if there is space , then arr[rear]=element ,rear++ lets say here 5 to push , checked whether it is full? It is empty , I put 5 where rear is pointing Lets talk about pop() , lets understand it If ( empty) , then you can't pop Queue is empty , when your front == rear What we learned above , whenever pop is performed it will happen from them the front i have to pop 5 I have to pop it , pop happens from front Remove it , and increment front Where currently front is pointing , I represent empty location with -1 , arr[front]=-1 increment front In this way popped it , one thing to keep in mind When we use this way it may be possible , if we talk about the last condition Now front is pointing here , 5 is here , we removed it and incremented front In short , now my front is pointing here , and rear also pointing here Now whichever element will be inserted , inserted in this way in short , this location is wasted Here put one simple condition , if (front == rear ) , then front=0 ,rear=0 Lets say while doing push/pop your front reached here , and rear here Now you will insert new element according to rear This space is wasted , that why will do front=0 ,rear=0 , when front==rear , we have to keep in mind isEmpty , it is easy , if your front==rear , then it is empty front() ,check if(empty) , then there will be nothing in front , return -1 arr[front] Lets move to its implementation and solve it I need array Then front , then rear then size in constructor , in input I am not getting the size I will give size by myself , 1st see the restrictions here In input format The no. of test cases , quarries So I took a big size size= 10000 arr=new int[size], as we used to do fixed initialization , we can do that also front=0 , rear=0 lets move to enqueue() , if full , we can't push if (rear==size) , here we have deed some mistake , lets say you pushed here something , your rear has moved ahead if rear ==n ,then it is full cout<< " queue is full" <<endl; in else , arr[rear]=data , rear++ How to do this ? if(front==rear ), in this case we call it empty , return -1 If it is empty then how you will pop in else , arr[front]=-1, front++ front==rear , if queue is empty , then front=0 ,rear=0 you have to also return the answer , int ans=arr[front], returned itlets talk about front Check whether it is empty or not , if it is empty then return -1 else , arr[front] if(front==rear ), return true , else false code is done , lets run it there is little issue make it qfront, it is getting confused in method name and data member , is there any more mistake Lets run it , correct answer , submit it Correct answer , so in this way implemented it You didn't told the T.C , it is easy In empty() , we are checking if condition , so its complexity is O(1) In push() , here also O(1) , in dequeue also O(1) In short , all operations T.C is O(1) If someone asks , did you know to implement queue ? yes Lets discuss 2nd concept , circular queue , what is it? It is an addition to normal queue this is a queue , my front is here ,, here I put 3 ,4 ,5, here is my rear I inserted more elements 6 ,7, 8 Rear is pointing to this I instructed to pop two times 3 ,4 got removed , now front is pointing to 5 Push 10 , it is done at rear , rear will be incremented In normal queue you will move from n-1 to n but in circular queue , if it gets full then you rear will go to here If now you say to push 12 , then it will be pushed here same with front , you popped this , then this , then this now it is pointing here when you popped this , it will go here We call this circular queue , everything is same , you should just understood this logic Are you understanding it? , lets try to understand the push() Here we will implement circular queue , we will implement all the logic Lets understand the push operation , here I will create a queue , so that you can get the idea This is a queue , I have two variables , which represents where queue it is starting and where ending , front and rear , both are -1 why -1 and not 0? You will understand while solving Both are -1 , if I push if full , it is full and you can 't more What is the condition? assume your front is here , and rear here This is the condition of full , if front==0 and rear==size -1, this is one way of full queue your rear comes back , and front ahead , because it is circular queue If my front is here , there is some element here is my rear , there is also some element This all would be also filled , this can be one more condition where queue is full if rear ==(front-1 )%(size-1) If it is true , then also your queue is full , this to condition represents that queue is full Then you can't do anything if( front==-1) , you are inserting 1st element Your queue is empty, you are inserting 1st element in this case front, rear=0 arr[queue]=data , in short we removed front -1 and pointed both to this location 3rd this is your queue Your rear is here , and one element has been inserted , and your front is here In this way it is filled , if rear is here so next insertion will happen here if(rear-1 &&front!=0) ,rear =0 and arr[rear]=data else rear++ , arr[rear]=data in this way I deed the enqueue() We will also do dequeue() same thing Lets write the code ,. I need an array then front , rear , size size=10000 arr=new int[size] front=rear=-1 if(front==rear&&rear==size-1&&rear==(front-1 )%(size-1)) in this case queue is full return false else if(front==-1), that you have got 1st element to be pushed front=rear=0, arr[rear]=value else if (rear==size-1&&front !=0) rear=0. arr[rear]=value else , rear++ ,arr[rear]=data It can be more optimized but this will run In all 3 statements you can see it, bring it out side return true In this way you have written the code If we go to dequeue operation /pop() , if(empty()) how will you pop it , your front and rear will be -1 then queue is empty next condition says that , for single element If queue contains single element , if(front==rear) here we will remove single element, it will become empty front=rear=-1 Lets move to next case, while popping your front again comes here , if(front==size-1), you will start from 0 4. normal case , here simply do rear++ , you got the answer Lets code it then move ahead , 1st i have to check whether it is empty or not? if(front==-1) , cout<<'' queue is empty'' <<endl; returned -1 , Lets move ahead , there is single element , then do like this if(front==rear), 1st I stored the answer arr[front]=-1 front==rear, then there is single element In this case , make front and rear =-1 else if (rear==size-1), in this case front will be 0 else , front++ You returned whatever the answer this condition is to maintain cyclic nature To check queue is empty This is to maintain cyclic nature , this is to push 1st element , To check whether queue is full this is your normal flow Here I am pushing Lets run it , will it run or not There are some wrong answers here we have given 'n' , so copy it Lets try again to run , still there is problem there is no need of this Ran it, all are correct submit it , correct answer We should have the confidence that we have written right code lets understand it again Lets talk about push() , 1st condition can be that it is full , 2nd that it is the 1st element As here we said front =rear=-1 , so we have to set it right , so I set them to 0 3rd , when I am pushing , you do it by rear , 1st here ,2nd here , like this And when we go to push next element , you have to come here from here if rear is at end then make it 0 4th, there will be normal flow , in this rear++ , arr[rear]=value In this way we coded it , 1st check the full condition then pushed 1st element , then rear=0, to maintain the cyclic nature we pushed 4 things , and tried to find the answer To pop 1st check whether it is empty or not 2nd , there is single element , when it will be removed queue will become empty , then front=rear=-1 3rd , we have to maintain cyclic nature , pop happens from front Pop from here , then it will happen like this When you will pop from here , then it should come here , your front ==size-1, then front=0 4th , will be of normal flow , just front++ In this way you have did this one also It is easy but you can get confused , so repeat it So till now we have seen normal queue , simple queue, circular queue There will be 3 more things , i/p restricted queue , this is your queue insert is allowed in one side only which is rear Here you will insert at rear only , but pop is available at both the sides In short , here is push_back() And pop_front(), pop_back() o/p restricted queue , if you have a queue Insert at both side is possible , push_front() ,push_back In output , it is possible from one side only , front side pop_front() If I have to tell you one more type , Doubly ended queue It is basically where we can performer 4 types of operations You can push and pop from here , and also from here , what do you mean by that push_back() ,pop_back () From here iot is push_front() ,pop_front() $ types of operations are possible . by doubly ended queue , you can implement both stack and queue , because Basic application is at CPU scheduling , it has been taught in our OS lectures , so and watch there What us practical use of queue , here we can perform 4 types of operation Is STL is available , yes Do you know the implementation? yes , lets do it Lets see the STL of doubly ended queue , after that we will take about the implementation Lets try to understand this , these 4 operation implementation lets create an array , so that I can explain you the implementation In starting front and rear are -1 If someone says push_front(), here also going to happen the same thing It is a circular queue with additional functionalities If push_front() comes , I have to push from the front if full ->it is not possible to enter more elements , we have already studied this 2nd, if you are entering 1st element if your front==-1 you are inserting 1st element , how it happens ? , we saw in circular queue It will happen at rear , in push_front , it happen with the use of front If I insert at rear , rear++, in push_front , if I insert something here , it will be inserted and front will move back Bhaiya we want to move ahead after inserting , we increment when we perform pop(0, as we seen above the normal queue if I pop from the front , then front++ , if I do the opposite , if I insert something , then front-- I am going to insert the 1st element , if some one says front==-1 , as we seen previously front and rear will be 0 3rd we have to maintain the cyclic nature , lets say my front is here , and I have inserted here now i got more push_front request I will go back , I have to come here , we have to maintain cyclic order , so n-1 if(front=0) then move it to n-1 4th, normal flow , front-- , arr[front]=value Lets understand it again , push_front say if my front is pointing something , if I get the push_front request I come back And insert it at that block , are you getting it? if your queue it full , then you can insert in it 2nd , you are inserting 1st element , in starting front and rear will be -1 , so you deed front =rear=0 3rd ,you have to maintain the cyclic nature , lets say , your front ia at 0 index You got push_front request , then you will move back , then you went here and pushed here If front is at 0 , you moved it to n-1 5th condition , normal flow , your front is pointing to this , you got the request , front--, arr[front]=value In this way you deed push _front If I get the request of push_rear() , I will say same , it will be same as circular queue Lets move to pop_front(), you have already done it ,we deed a circular queue question , when we do pop , we use to do it from front same that you have deed in that next , pop_back , I have to pop from the rear , lets do this I have 4 conditions , by using them i will implement it , this is a queue and I have to pop , 1st thing , if(empty()) , then you can't do it 2nd , you have single element , in that case , it will be removed your queue will become empty , front=-1 , rear=-1, we have done it in circular queue 3rd , maintain the circular nature , lets try to understand it When I pop back , how will I do it? It happens from rear , 1st write the push one , if rear is here when you get push, then you used the move forward , and use to insert there In same way when you get pop request , you will remove it, and rear-- In cyclic nature , you rear has reached 0 , and you got the pop_back request , you will come here In short , if (rear==0), rear=n-1, 4th case normal flow , rear--, in this way you coded it, it is easy to code It is same as circular queue , there is nothing additional , but you have understood doubly ended queue , we will code it Lets see the STL I will comment this I have to create a doubly ended queue of int type we have already included it , I want to perform d. , see there are many operations I want to do push_front(12) , lets see what happened ? this is your queue , in front you inserted 12 I want to do d.push_back(14) In short , at back I inserted 14 Print it front means we will see from here , it should print 12 , if I see from back then 14 d.front() , and also d._back() My answer should be 12 , 14 we will see from here , it should print 12 , if I see from back then 14 cout<<pop_front()<<endl, it removed 12 there is only 14 this is my front and rear , if I try to see it again It should give 14 in both, run it d.pop_back , It also popped 14 now my queue it empty , now if I have to check if (d.empty()) , cout<<'' queue is empty''<<endl; else , cout<<''queue is not empty''<<endl; Lets clear and run , it should give queue is empty ,how? I pushed 2 elements and popped two times So here we implemented doubly ended queue by STL Go toc cpp reference and see , and what you can use Here I have to implement it , lets try to implement it , we already know the logic 1st we will do push_front() I need an array , then front , rear size , size=s ,allocate array dynamically front=-1 ,rear=-1 lets talk about push_front() I have to check the full condition if front is here and rear here , ere I will take it I will use it If full , in this case return false , I can't insert else if , you have to insert 1st element , front==-1 , front=rear=0 else if , you want to maintain the cyclic nature If your front==0, you have to do front =n-1 else , front-- then you store the value In this way you have written the code In this way I will copy the push_rear() code , 1st case will be same 2nd case , if single element then it will run like this If front ==0, here I have to paste the previous code In this case , rear=0 rear++ In this way you have coded it Did I made any mistake here? rear==size -1 && front !=0, it means rear is at end and front is at somewhere ,, there is space available , so I pushed here In same way I may have to update this condition , front is here and I have to move it here rear should be here Here I deed &&rear !=n-1 pop_front logic will be same , we copy pasted We went to pop rear , lets understand how to do it , 1st case is same Check whether empty or not , if empty then returned -1 We have to do it from rear Next condition is single element , else if , rear==0 In this case , rear =size -1 Normal , rear--, in this way you written it We have deed small changes in previous code here we are checking isempty condition return -1 , or return arr[front] , getrear will also run in the same logic How will you check empty? if(front==-1 ) , return true , else return false How will you check full , so paste it in full also We know that this is full part , so call the isFull() This part is of is empty , so I made the isempty() isFull(), here will be isEmpty condition here also isEmpty() If you write here then also it will run , so we have coded it lets run it , it will become clear to you, there is some problem we have to write size Lets run it again , one test case is coming wrong Checking... Checking ... There can be problem , if front=0, rear=n-1 , in short I said this is my queue Front is here , and at last is rear , and your queue is full front is at 0 and rear is at n-1 , so it will be full , right rear=(front-1)%(rear-1), this is the condition , rear is just behind the front front=rear+1 Basically the size of array , there can be one thing where front =0 , front-1 , it will be negative -%(rear-1) , it will be 0 , here is the problem If I put one condition , front !=0, will it run Run it , all test cases has been passed , now submit it Correct answer In this way we solved this , I can understand If someone asks , tell the implementation of simple queue , i can tell I can also tell circular queue , and doubly queue also All operations happens in O(1) , it is not hard , if we have understood the circular queue implementation , then doubly ended is similar to it here I am just modifying it In this way we have solved 3 questions , we will meet in the next one Tell me in the comments how is the video? Now the time is 1:29 am That's it for this video , will meet in the next one , Bye Bye!1