4.6 Implement Queue using Stack in C| Data Structures Tutorials

In this lecture we are going to see how to implement a Q using stacks. See first of all we will discuss the process of implementing a Q using stacks with the help of an example. Then we will write down the code for this thing. Fine. So now I hope everybody knows what is a Q and what is a stack because we have already discussed about Q's and stacks. You can find out the link of those videos in the I button as well as in the description box. Fine. So Q follow which rules? FIFA rules? First in first out. It means insertion would be from one end that is from rear end. Deletion would be from another end that is from the front end. We are having suppose this is what our rear end and this is what front end. And both insertion and deletion operation should take order of one time complexity. Right? As well as in case of stacks it follows what? Leo rule. Last in first out in this case logically we are going to represent Q something like this and stack something like this right so we can this is what it is having just one end open that is top you can insert from here you can delete from here that is the only choice you have so now here the question for you is you have stacks push and pop operations of the stack and what you need to do you have to implement ment this Q using stacks. You have to implement NQ and DQ operations. You have to follow the property this FIFO property using this stacks. You can say you have to implement this property FIFO property. This is what Q. So if you want to enq some operation at starting what both front and rear would be minus one. We are using arrays to represent a Q here and both stacks. Fine that we have already discussed how to implement a Q using arrays as well as how to implement a stack using arrays. You can check out the previous videos. Now suppose I'm calling this NQ operation three times. It means five would be inserted from rear part here five here two and here we will insert now three. So now at this point of time front is pointing to here. It means front is zero and rear is what? Two. Right? Now see simply we have this stack you have to implement this thing means you have this one here you can insert this is I'm just showing you how the operations would be performed in Q but you don't have Q you have stacks right you can use one stack two stack three stacks it's up to you but you have to implement this Q right so now first of all five so five we can insert we can push in the stack then two we can insert then three we insert fine now if I'm calling dq operation so now which element from the q should be deleted the element from the front only so here the output should be five and after deleting this five here you can see this front would become one now the problem is we have one stack right now if you pop one element from here which would be popped three would be popped Because here we want the output should be five because we are implementing here Q right. So how you can pop this element from this stack right. So now you can do one thing. See we can take another step and what you can do when a dq operation is there then all the elements from the stack one would be popped out one by one and pushed in stack two. Means three would would be popped out and we will push three in stack two. then two and after that five and now pop one element from stack two. If you pop one element from stack two then five would be the answer and that's exactly we want the output of this dq should be five. So here the situation is what you have to use two stacks to implement a Q. And now after popping this five what we can do again we will pop all the elements from the stack two and push it in the stack one. So means two here in this stack one be one would be pushed like here we have nothing then two then three now this is what stack one right we don't have anything in this stack two now again if you call nq suppose I want to insert here seven simply insert simply you can say push in stack one that is seven so here we can push seven so you can say NQ operation on stack one and dq from stack two. This is how you can implement a Q. Now see here two approaches can be there to implement a Q using stacks. What are those those approaches? See now. So here are two approaches two methods to implement a Q using stacks using two stacks. Basically you can implement a Q using one ST only right using the recursion calls but here we are discussing how to implement a Q using two STS. So now first method is here NQ operation would take order of one time complexity but DQ operation would be take taking order of N time complexity. So it means DQ operation would be costly in this case. Second method is here NQ would take order of N time complexity and DQ is taking order of one. So here in this case NQ operation is costly. Right? So here can you tell me which approach I have discussed with the help of this example. See I'm going to tell you here whenever we are performing NQ operation then simply what we did we simply push the data in stack one. We didn't nothing we just increment the top push the data into into stack one. So it is going to take order of one NQ operation. But when we are performing DQ operation in that case what we did see first of all we popped out all the elements from stack one till this stack one becomes empty and push all the elements in stack two. After that we pop out the first element. After that again we pop all the elements from stack two and push in stack one. It means what we have done the dq operation is going to take order of n time complexity right suppose three n value is three in this case so all the three elements you will have to push here right again after that after deleting the first element the top element again the n minus one element you are going to push in stack one so two times you are going to perform the these operations on the data right so that is why it is what proportional to n it is you can say in big notation we can say order of end time complexity so here in this case in this video I'm going to discuss the this approach approach first one you can use this approach also that also we'll discuss in the next video fine so I hope you got it how you will implement this approach so now I'm going to write down the code for this thing so now here in main function I'm calling this NQ operation three times I want to insert I want to enq in this Q the First of all five then two then minus one then I want to dq one element then again nq one element and then display fine so now see we are going to take we are going to use two stacks for this and we are going to implement this Q this is just to make you understand how exactly Q is working we don't have this Q actually we have only two stacks with us in the program only see I have taken two STS S1 S1 and S2 right and I have taken that macro definition n is equal to 5 wherever in the program I'll use this n variable then that would be replaced with this five so it means you can say both s1 and s2 is having capacity of five we can store only five elements right so you can say in a q we can store only five elements because we are implementing a q right so we will actually push and pop data from here but I'm going to show you how actually that nq and dq operation is going to perform in Q also fine So now see obviously we are taking top one two elements would be there this first stack one top one is there and for this top two is there both top one and top two are initially pointing to minus one there is nothing in this step right now first of all I'm calling this NQ operation then then now the control will go to to the definition of this NQ operation right so now let us define this NQ operation see here I'm passing five. So here also you need something to receive that five value. So here I'm taking a variable x. Right? Now x is equal to five. That thing I want to insert here. Nq operation is going to perform in which stack? We have discussed in stack one. Right? So here I want to push s the data x. DQ operation would be performed on stack two only. Right? So now here you will call what? push right and what element you want to push five now here in X I have five so I'll pass here X now we are taking one more variable that is count ++ why I'm taking this count see suppose I have inserted five 5 2 and here minus one now I want to perform DQ operation in that case what you need to do you have to pop all the elements from stack one and push here. Right? So first of all I count how many elements are there in the stack and we are going to pop the elements from stack one till that count variable reach to zero. Fine that is why I'm counting the number of elements the number of data in the stacks that is why I'm taking a count variable. So this count variable obviously we are going to declare here suppose I'm taking int count is equal to at starting I'm initializing it with the zero. Now see here also we have one problem. See push we are going to perform push on stack one also on stack two also. So you have to differentiate that function. So here I'm performing this push operation on stack one that is why I'm taking push one here not push here I'm taking push one operation. Similarly we will take pop one and pop two right now see again control will go here. Now this is what again a calling of a function that is push one. So obviously you need to define it somewhere before using this function calling I guess you everybody knows the rule is before the calling of the function there must be either the declaration of the function or the definition of the function right that thing I guess everybody know if you don't know then we will discuss this thing also when we are going to start the C programming right I'm defining this push one here see now here this x value would be passed so obviously In definition also you need something to receive this value. So you need a variable here int data or x same variable name you can take it's up to you right or ab c as you wish. Now in push we are going to check the overflow condition also if you want right. If the top is pointing to here that is four. It means s1 is full we cannot insert any data or you can say q is now full right because obviously we are ultimately implementing a q. So here you can write if top one because push one means we are talking about this stack. So top 1 is equal to is equal to n minus one. Here you can simply write overflow condition. Right? Else else we are going to push here. The first thing is top 1 ++ we are going to increment the stop. Now top is zero means stop is pointing to here. Now you can push here the data. So now what you can do in stack one see here I'm writing this variable name is data because here I'm taking the variable name data you cannot write x here you cannot take this x because this is what a local variable you can use it within this function definition only you cannot use here here I'm taking data that is why I'm taking here data so this is what a push one operation definition of this one now see what about this dq operation. Now when control will go to the dq operation then what will happen? See now first of all see what is the situation after calling the three times NQ operation. First time NQ will be called then control will go here five push one five. It means here the control will go to here. Here this is a function called the control will go to the definition of the function. Right? Suppose I'm writing this definition of push one operation before this NQ operation. Right? Otherwise if you will write here after this one then it will give you an error. You have to declare this push one before this calling. Right? Now the see the condition is top one is equal to n minus one. This condition is not true. Else control will go into else part. Top 1 ++ means top is now zero. S1 0 is equal to data. So data is what? Five. So five will be inserted here. Again call the NQ here. X value is two. Push one. Two would be called. Now see one thing again after this calling the control will go back to here and count ++. Now count becomes one that you need to take care. Now here you can see count becomes one. Right? Again NQ means here two would be passed. Here two would be passed. In data I have two. This condition is not true. else top 1 ++ now top is having one it means top is pointing to here right now s1 top here I want to insert data data value is what two so here you can insert two again control will go again back to here where the function calling is there now count ++ now count becomes two nq minus one x value is minus one minus one will be passed here this condition is not true again top one plus now top is two so top is pointing to here. So here I want to I can insert here minus one. Now again control will go back to here. Then next statement is count ++. Now count becomes three. Right? Now see what the next is what dq. Now how you will dq? See I have told you the processor. First of all pop all the elements until the stack one becomes empathy. Push these elements in stack two. After that pop from stack two. See this process for dqing. First of all pop all the element from s1 push here then pop from s2 then again remaining element would be pushed back to s1. This process is what you can say it is behind the scene process. It seems like you are implementing a you are using a only right. This process is behind the scene. Fine. Now in dq what you will do first of all popping off this one. So obviously you need to you need a loop right? So now I'm taking a for loop here. First of all you can check if there is nothing in stack one and stack two then you cannot pop anything means Q is empty. So here you can write if top 1= to minus1 and top 2= to equal to minus1 then here you can print simply Q is empty. else in else part what you will write obviously we are going to pop these elements so we need a for loop four I'm taking a variable I I is equal to zero so see I'm taking a variable I so you need to declare I here right in this function and I less than count till then we are going to execute the statements written in this for loop and I ++ Right now what you are doing see first thing is pop this one from S1 and push here. So first is what pop operation call the pop operation. So you can say pop one because pop operation we are calling on stack one. So this pop one will return minus one. So we are going to store this minus one here in another variable you can say a. Fine. Now in a I have minus one. Now I'm pushing this minus1 in stack two. Right? So now we are calling push two operation. Right? Because I'm pushing here. We cannot use push one. We will use push two. Right? So here what you will pass the value in a that would be passed. Right? And that's it. If you are not writing in two statements, then you can simply write in one statement. What you can write? Push two. In this bracket, simply write pop one and this function. See, we have done what? We have popped minus one and we have pushed minus one here. So after popping minus one, this top one value becomes one. So now this is pointing to here. Right? Now what you will do again this two would be popped out because this is what a while loop sorry this is what a loop. So it is going to continue till this i value is less than count and count is three and i value is zero then i value becomes one then i value becomes two means three times this loop would be executed. So three times means 1 2 and three. All the values we can pop and pushed in stack two. So after that this two after that this five. After popping all the values this top one value becomes minus one again. Right? And here the top two becomes value becomes now two means top two is pointing to here. Now next thing is you can now you will pop out from stack two. So now here you will write what pop two because we are calling pop operation on stack two. So pop two whatever suppose the value this return pop two return we are going to store in a variable B and if you want to print the popped or the dqed element is so here simply you can write print f the dqed element is I'm not writing the complete sentence and here you can print this b right so you are taking here b and a also so here you are you need to declare a and b also in this function definition right now this is not yet done. What you need to do now? Again see after popping this we have popped out this five right and we have the output is we have printed this five right and according to Q what should be the output C NQ 5 then 2 then minus one and if you perform DQ then from the front it would be dqed so output would be five and we are getting five only it means we have successfully implemented both NQ and DQ operations on stacks And we have implemented a Q. Now what you need to do again pop these elements from here and push in stack one again. So now this is not yet done. What you need to do after maybe you printing this dqed element in the q now I have only two element because I have nqed three element one element I have dqed. So basically count should be now two. So you have to decrement this count now. So after this line whatever you will write I'm writing here because I don't have so much space. Now count minus minus right. So now count becomes two. Right? Because actually we are having only two elements. Now we are going to again push back these elements into stack one. Right? So again you will write down a for loop for i is equal to0. I less than count. Same for loop. I ++ and now here the situation is we are popping from stack two. So first of all we will call pop two. Here we are calling pop one. Whatever this will return. Suppose I'm storing in a now in a I have two right? Now this top two is having one after deleting this right after popping this. So now I'll call push one because I'm pushing in s1 right and here I'll pass a and this is it. So after executing this loop the the situation of these stacks would be we have inserted two here then minus one here. So now top one is having value one and top two is now having minus one one because we have deleted this value from this. Now this is the situation. Now in stack one I have two elements. Now see here in dq operation I'm calling what? Pop one also, push two also and pop two also. So you have to define these operations also because we have defined only push one. Right? Now I'm defining what? Pop one operation. Right? So now I'm taking int pop one because this is going to return a value and that value we are going to store in a that is why I'm taking here the rate type is int here you will return what value you will return in pop one means here on stack one right so now what value you will return from stack one right and in popping I guess everybody know first of We are going to return the value. We are going to take out that value. Then we are going to do top minus minus. Then we are going to decrement this top. Right? So now means the decrement would be post decrement. After fetching the value after that we are going to decrement not predecment. Fine. Here in push in push this is what? Pre uh increment. So here this is pre-increment. Here the decrement would be the post decrement. So here you can write first of all fetch the value of top one. Right? Now do minus minus. That's it. This is the definition of pop one. Simply for pop two int pop two. And here what you will return return here stack name is stack two because we are performing pop two in stack two. And here top two whatever the value in top two that would be returned and after that we will do top minus minus. So that is post decrement. Now what about this push two? This is same as push one. The only difference is what here you will write push two. Fine. In top we are checking condition on top two. Right? Now here we will increment top two and we will push the data in top two and here you will write s_ub_2 s2 top two that is the only difference. So now this is the code for this NQ and DQ operation. Now you can trace out this code after calling again NQ and DQ operation. So I'm not going to trace out that thing because video would be very lengthy. I have traced out for one instance that is for five only. I have showed you how the output would be five and in Q also the output should be five. Now we will see how to display the content of the Q. So now here what should be the output of this display function 2 and minus one. See 2 minus one because five we have already dqed from the que right we don't have this Q actually this is just for you guys to make understand fine we have these two STS. So the output should be 2 minus one right now see we cannot print from here minus 1 and two because according to the Q we are implementing Q. So the output should be 2 - 1. So now we are going to display whatever the content in stack one. Why stack one? Because stack two is only a temporary type of stack or you can say it's a supportive step. When you are performing the DQ operation, then only we are going to use the stack two. Once DQ operation is done, we push all the elements of stack two to stack one. Right? We pop all the elements from ST two and we push all the element in stack one. So actually we are maintaining the data in stack one only. Right? This is just a supportive stack. So finally the data would be in stack one. I'm ensuring that the data is present in the stack one. So whatever the data present in stack one, we are going to display that thing and that should be the output of the que. Right? So now how we are going to display this thing here? We have two elements. So we are going to use a for loop. I'm taking a variable I. I is equal to0 and I less than equal to top 1. Here's see in stack one I'm taking the variable top one and I ++ and here in this for loop you will simply print the value what see the name is S1 and in subscript you will pass I. You are taking a variable I. So here you have to declare a variable I right here simply you can say that print f the Q is before this for loop you can write down in print fine now see you can see the working of this for loop I is equal to 1 at starting I less than equal to top see top one is one and zero is less than equal to 1 condition is true that is why we are going to enter into this for loop print f percentage d stack one i means whatever the value at zero index that would be printed in stack one at zeroth index two is there so output would be two right again I ++ now I becomes one see the condition one is less than equal to 1 because top one is one yes condition is true again we will enter into this for loop s1 whatever the value at first index that would be printed that is minus one would be printed now i - i is equal to two now now see the condition is 2 less than equal to top one no the condition is not true. So we are not going to enter into this for loop. We are going to exit from this for loop. Now here also you can ask one question. Can I write here I less than equal to count because count is also two. Right? So two times this loop would be executed and two and one would be printed. But if you write here count variable then there would be some problem here. So now I'm leaving this question to you only. You need to find out the answer. You will write down here count. You will implement this thing and you will tell me in the comment box what problem you are facing. If you write down here this count. So this is how you can implement a Q using STS. See this is not the only way you can implement Q using STS. There can be many possible ways. Right? Using one stack also you can implement using two STS also implement but you will not follow this approach. You will not take this count variable and you can apply your own logic. So this is only just one way out of all the possible ways. You can develop your own logic and you can implement this Q using stacks. Right. So now in next video we are going to see how to implement a stack using cues as well as we will see I'm going to start about trees. We will see the introductory part of trees. Fine. So I'll see you in the next video. Till then bye-bye. Thank you.