In this lecture, we are going to see what is circular queue and how to implement circular queue using arrays. See, we have already discussed how to implement a queue or you can say a linear queue using arrays and as well as using linked list. Right. So you can check out those videos in the description box.
Fine. Or in the side button also. Now, see in that video implementation of queue using arrays, we have discussed a major drawback of the linear queue implementation.
So to overcome that. drawback this circular q concept comes into picture right see now what is that drawback this is what a q q concept is what it is basically uh following the rule fifo rule first in first out means insertion would be from one end that is from the rear end i am taking this end is rear end and this is what front and deletion would be from the front only right and deletion and insertion is going to take order of one time complexity fine you Now let us take this one example and we are going to discuss again that drawback of the linear Q. This is a Q I have specified the size of the Q that is 5 only right.
Now suppose in this Q I have called the function enqueued 5 times right it means here I have 2 minus 1 5 6 and 7. How we are going to store the data here that thing we have already discussed in detail in the previous video implementation of Q using arrays you can check out that video in the side button. first of all check out that video then i recommend you to come to this video fine now this is the q now again if you call nq function in that case it would show what the q is full so what is that condition the q full condition is what at this time front is pointing to here and rear is pointing to here means in front i have zero you can say front is equal to 0 and rear is equal to 4 right from the rear only we are going to insert so when you will insert rear plus plus then we will insert right now see if the rear is 4 it means the rear here is this maximum size minus 1 it means q is full that is the condition now after nq operation i have called dq operation right now dq means we are going to delete data from the front of the q so this would be deleted it means front plus plus we will do so it means front is pointing to here right it means this is the garbage value now only the data between this front and rear this this is now our q we don't care what garbage value lies here we Because we can overwrite this value. Suppose I am deleting this. Right.
Now again if you call nq function. In that case also it will show what? The q is full. Why? Because we have set the condition of full.
What? If rear is n minus 1. That means it will show q is full. Now suppose again if you dq. Again call this dq operation one more time. Then front is pointing to here.
In this case also it will show q is full if you call nq function but we have the space still we have space but we cannot insert here this is what wastage of the space this is the major drawback of linear q. Now what if we modify our this function nq and dq operation and After modifying something, this rear, when we do, obviously we will not do rear plus plus, when we will increment rear, then it will point to here. Now if you call that NQ again, in that case, now see this rear is pointing to here. At this point of time front is equal to 2 and rear is equal to 0. Right.
And now obviously insertion would be from the rear end. So we will insert here only. Now suppose I am calling NQ minus 1. So I can insert here. right and this is not a wastage of space we are utilizing this space now again if you are saying nq suppose 4 we will do what in that case rear would point to here and here i can concert 4 in this case now rear is equal to 1 right but now q is full so now that condition the full condition the q is full condition you have to modify a little bit what you will do see in this case q is full now but rear is not 4 rear is not n minus 1 rear is 1 and front is 2 how you will write down that condition see if you write here rear plus 1 mode n means size of this queue equal to equal to front it means queue is full you can check in this case rear is 1 1 plus 1 That is 2 mode n value is 5. 2 mode 5. So 2 is equal to is equal to what is front value? 2. 2 equal to 2. It means Q is full.
And see Q is full as you can see. So you have to modify those condition a little bit. See now how we will write down this in Q operation and D Q operation coding. So now one thing we have discussed that. front and rear are pointing to minus 1 starting at starting it means q is empty that condition we are not going to change fine so at starting we are going to point both front and rear is equal to minus 1 right so NQ function I am calling link 2 so here you you need something to receive that value integer value integer x so now in nq also we will check if the q is empty means both front and rear equal to minus 1 in that case after inserting data here both front and rear would point to here we will also increase rear as well as front means both front and rear becomes 0 this condition you have to check so one case in nq function is what if front equal to equal to minus 1 and rear equal to equal to minus 1 or simply Simply you can say front equal to equal to minus 1. In that case you will set both front and rear equal to 0 first of all.
Right. So now both front and this rear are pointing to here. And now you can insert. For inserting we will use this one rear.
Right. So Q of rear is equal to X. This is one case. Now suppose I have inserted here 2. right because at starting when we we will call this one then this condition would be true because at starting both are minus one and minus one now two cases are remaining second second case may be when the q is full then we cannot insert third case may be q is not full but we have some element in the q right so now we will check for that case the q is full you can check that condition here also at starting also fine after that you can write this condition it's up to you now i'm writing else if now Now I have told you what is that condition. We will not write rear equal to equal to n minus 1 as we have discussed in previous video.
Because this is now the circular cube like this one right or you can say this one. Logically you can represent this array something like this right. Now else if what is that condition rear plus 1 mode n equal to equal to front.
Here simply you can print q is full. Right. You can say overflow condition.
We cannot insert. And this condition I have discussed in detail in this video only at setting of this video. Why I am writing this thing.
Now third condition may be this one. Q is not full but Q is not empty also. is having one element now what you will do now in this case we will not do rear plus plus how you will increment this rear because when you will do rear plus plus suppose rear is pointing to here and if you do rear plus plus means rear becomes 5 but we want rear would be 0 after that so we cannot do rear plus plus what you can do rear plus 1 mode n. This thing we are going to store in rear. So simply you will write.
Now rear becomes rear plus 1 mode n. Right. And now you can insert q of simply rear is equal to x. So, this is the n q operation. See.
Secondly, when we are calling for minus 1. In that case, this condition is true. No. This condition, check. See.
Rare equal to 0. 0 plus 1 means 1. Modulo n. n value is 5. 1 mode n it will give the remainder that is 1. 1 equal to equal to front because front is 0 but 1 is not equal to front. It means q is not full. We are not going to enter into this part right.
See this this modulo n. condition this will affect only when rear becomes 4 after that it will become 0 otherwise same it will it will have the same effect as rear plus plus right see i'll show you now this condition is also not true now else part rear is equal to rear plus 1 mode n now rear plus 1 rear is 0 0 plus 1 mode n value is 5 1 mode 5 that is 1 only so now rear become 1 as you can see after 0 here become 1 means rear plus plus na right so now q of rear q of 1 is equal to x means here i can insert minus 1. again i am calling 5 6 and 7. for all these three the control would go here you can trace out this one so simply we will insert here 5 6 and 7 and now rear is pointing to here now we will discuss first of all the dq operation right how you will write down that code in dq also first three cases may be there if q is empty so we can not dequeue anything we cannot delete the data for empty the same condition front is equal to minus 1 rate equal to minus 1 in that case you will write here we have written this thing but here you will write q is empty or you can say under flow condition right if this minus 1 condition then here you will write q is empty i am not writing this thing else if now second case may be in the q we have only one element left this thing we have already discussed i am not going into detail so if one element is there in that case both front and rear would be pointing to that element right now if front equal to equal to rear right suppose we have dq'd these elements suppose i have called four times dq means four times one two three four the now after dqing four front is pointing to here it means we have only one element left see both front and rear are pointing to same both front and rear are four right so it means we have only one element if one element after deleting this element both front and rear means should point to minus one means after deleting this the key Q would be empty and what is that empty we have taken what condition when front and rear are minus 1 in that case Q would be empty so here you can set front equal to rear equal to minus 1 that's it now the third case third case is suppose this one else and if you want to print the dq element right suppose here i want to print that 7 so before setting both rear end this front minus 1 before this line here you can write print f the element is percentage d you and what you can print q of front because dq would be always from the front so we will use this front we will not use this rear although both are pointing to the same thing but we will use front so you can print q of front right now this case third case is this one q is not empty and q is not having one element q is having more than one element in that case simply what you will do we will obviously we will increase this front but we will not do front plus plus because this is circular q once front reach this point it should point to zero and if you will do front plus plus then it would point to five but it should point something like this so here also you will do what now front equal to front plus 1 mode n the same condition right and if you want to print the dq element then simply before updating this one here you can write printf the dq element is %d and here you can print q and in subscript you will write front now see the working of dq i have called this dq here now check this is the q after calling these five nq operations now dq empty condition is not true else if front equal to equal to rear but this condition is also not true because front is 0 rear is 4. So now we will go into else part print f the dq element is q of front means q of front means 2 would be printed right and now front equal to front plus 1 see front is equal to 0 0 plus 1 mode n value is 5 1 mode 5 is 1 only so now front is 1. And this is same as front plus plus. The only difference you will see when front becomes 4. After that it will go to 0 not 5. Right.
And that's exactly we want. Because we are implementing circular Q. Now.
This is garbage. So we can delete this now. Right.
Again suppose I am calling DQ function. Now this condition is not true this condition is also not true. So control will go into else part dq front would be printed that is minus 1 would be printed in this case. In this case 2 would be printed. Now front equal to front plus 1 this one.
So now front is 1 1 plus 1 more. 5 means 2 mod 5 means 2. Now front is 2 and that's exactly we want. This is now garbage value. Right.
Now in this case again I am calling nq function. Now you will get this thing. nq 0. N q 0. X value is now 0. This condition check. Is this condition true? No.
Because front is not minus 1. Rear is not minus 1. Else if rear plus 1. In this case rear is 4. See. 4 plus 1. Mode n. n is also 5. 5 mode 5. This is 0. Equal to equal to front value is 2. See front is pointing to here after calling 2 dq. Front is 2. Is 0 equal to 2? No.
It means we are not going to enter into this condition. Means it will not show you that q is full. Right. In else part. See.
Now rear is equal to rear plus 1 mod n. First of all modify the rear. Now rear is what? 4. 4 plus 1 mod n.
4 plus 1 mod n that is 5. So it means 5 mod 5 that is 0. Now rear becomes 0. So now in this case rear is pointing to here 0. Now you can insert q of rear q of 0 is equal to x. x value what we have received 0. So here you can insert 0. But this is not the case in linear q right. In that case it will show you q is full if the rear is pointing to here.
Now see again we are calling in q. function see this condition not true check out this condition rear plus 1 rear is 0 0 plus 1 mod n 0 plus 1 mod 5 that is 1 only 1 equal to equal to front is 2 no this condition is not true so we will go into else part now rear plus 1 mod n 0 plus 1 mod 5 that is 1 only so now this rear is here here and front is here so right, rear is 1, front is 2, now we can insert q of this 1 is equal to x, x is 10, now we can insert here, right, now again I am calling nq and I want to insert 11, so x value is 11, this condition not true, this condition, now check this condition rear plus one rear is now one one plus one mode five that is two mode five two mode five is two and front is two now this condition is true now control will enter into this loop and it will show you the q is full as you can see q is full so now these are nq and dq operations in circular q right you just have to modify a little bit this condition rather than rear plus plus rather than front plus plus and the q full condition would be something like this somewhere this condition is also written something like that if this front equal to equal to rear plus one see front is 2, rear is 1. So, front is equal to is equal to rear plus 1 that is 2. In that case, q would be full, fine. You can write down this condition also, but in that case, you have to write down some more condition for this full.
Because in that case, you will also write if rear is equal to is equal to n minus 1, in that case also it is full. So, rather than writing 2 or 3 conditions, simply write 1 condition and that is it. That will cover all the conditions, right. Now, we will see how to display.
the data so now i guess you remember in the previous video when we were discussing the linear queue implementation using array we have discussed how the display condition we have written what for loop i is equal to front and i less than equal to rear plus plus one till then we are going to print but here we cannot write down that condition suppose i am taking here also i is equal to i is equal to front means now i is equal to front means two so Or i less than rear plus 1. This was the condition right. I guess you remember. So i now 2 less than rear plus 1. Rear in this case is 1. 1 plus 1 that is 2 less than 2. No this condition is not true.
So it will not print anything. Because this is circular Q. So we cannot write down this condition.
You have to modify this condition also. Fine. So now here I am writing what.
While this i not equal to rear. Fine. Till then we are going to print.
See I will show you the working of this also. Print f percentage d q i. Fine. And how to increment i?
I equal to here nowhere we will write rear plus plus front plus plus or I plus plus something like this. Increment would be same we have discussed like this. I plus 1 mode n because we always want when some way.
variable reach to here then it should point to here means in circular motion and this is the condition for that thing now i'm taking i so here in this function after in this function you can take i and you can initialize this i with front now i'll show the working of this thing see at starting i is equal to we have taken i and i is equal to front front is now 2 so i is 2 this Condition is not true because Q is not empty. Fine. Else, now the Q is, while I not equal to rear, I is 2, rear is 1. Condition is true. Control will enter into this loop.
Print F Q of I means Q of 2, Q of 2 that is 5 would be printed. Right. Now how you will increase this i. i plus 1. i is 2. 2 plus 1. Mode 5. 3 mode 5 that is 3. Now i becomes 3. Fine.
Same as i plus plus. Now i is here. i is pointing to here. Fine.
Check again. 3. i is 3. 3 not equal to rear. Rear is 1. Fine.
See here you can see rear. is equal to 1 and i is 3. Yes condition is true. These are not equal.
Again q of i would be printed. i value is 3 means q of 3. 6 would be printed. Right?
How to increment i? i plus 1. 3 plus 1 mode 5. That is 4 mode 5. That is 4. Now Now I becomes 4. That is here. Check 4 not equal to rear.
Rear is still 1. Yes condition is true. Again print Q of I. Means Q of 4. This 7 would be printed.
Now how to increment I. We cannot do simply I++. Like in that case. Fine.
Because we have to move here. Now see. I is 4, 4 plus 1 mod 5 that is 5 mod 5 that is 0. Now I is 0. Right? So now I is pointing to here.
Now check. 0. equal to rear is 1 yes condition is true 0 is not equal to 1 control will enter into this loop print f q of i q of 0 that is 0 would be printed now how to increment i i plus 1 now i 0 to 0 plus 1 mode 5 n value we have taken 5 1 mode 5 remainder is 1 only now i is 1 now i is 1 now check i is 1 not equal to rear is now also 1 but 1 is equal to 1 so this condition is now not true so now control will not enter into this loop control will go out from this this while loop here here right but now the problem problem is we have only printed 5670 5670 we are left with one element still so now after this while loop here simply you can write printf %d and q of rear See as you can see. Now control will go out from this loop print f percentage dq of rear. See rear value is 1 now. So now q of 1 would be printed that is 10 would be printed.
And i is also 1 so here you can also write q of i simply. So this is how you display the data of a circular queue see it is not like that this is the only way to write down the display function maybe using for loop maybe using some other condition here rather than writing here you can use if you don't want to print this value separately so you can use do i loop also also many methods can be there to display the data fine correctly fine so this is only the one way out of all the possible ways right now we will see the this peak operation see this is very simple and i guess no need to write down the code for this thing because this is same as we have discussed in the previous video you can check out for empty if both front and rear minus one then q is empty else part in else part what you will write you just have to print whatever the value at front of the queue means at front of the queue now at this time 5 is there so here simply in else part you will write printf %d queue front That is it. No need to do any increment.
So, this is same as we have discussed in the previous video. Only difference is in NQ, DQ and this display operation. Fine. So, this is how you can implement a circular queue using arrays.
In next video, we will see how to implement queue using stacks. So, I will see you in the next video. Till then bye bye. Take care.