5:11will be -1. To check whether Queue is empty or not
5:15we can simply check the value of front and rear
5:19and if they're both -1 we can say that Queue is empty
5:23I just wrote isempty function here. -1 is not
5:27a valid index. For an empty Queue there will be no front and
5:31rear. In our implementation we are saying that we will represent
5:35empty state of Queue by setting both front
5:38and rear as -1.
5:42Now let's write the enqueue function. Enqueue will take
5:45integer x as argument, there will be a couple of conditions in enqueue.
5:50If rear is already equal to maximum index
5:53available in array A, We cannot insert or enqueue an element
5:58in such scenario we can return and exit.
6:02I would rather use a function named isfull to
6:05determine whether Queue is full or not. If Queue is already full, we can't do much we
6:10should simply exit,
6:11else if Queue is empty we can add
6:15cell to the Queue, we can add cell
6:18at index 0 in the Queue, and now the we can set value at index
6:23rear as x. In all other cases, we can
6:27first increment rear, and
6:31then we can fill-in value X at index rear.
6:34I can get a statement a[rear] = X outside these two conditional statements
6:40because it's common to them, so this is my enqueue function.
6:44In the example array that I'm showing here let's enqueue some integers.
6:48I'll make calls to enqueue function and show you the simulation.
6:52In the figure here, let's say first I want to insert number 2
6:56in the Queue, I'm making a call to enqueue function passing
6:59number 2 as argument. The Queue is empty, so
7:03we will set both front and rear as 0.
7:07Now we will come to this statement, we will write value 2 at index 0.
7:12So this is Queue after one enqueue operation, front and
7:15rear of the Queue is same. Let's make another call to enqueue,
7:19this time I want to insert number 5. this time Queue is not empty,
7:23so rear will be incremented. We have added
7:27a cell to the Queue by incrementing rear and now we will write the value
7:315 at the new rear index.
7:34Let's enqueue 1 more number. I have enqueued 7.
7:38Let's not write dequeue operation. There will be couple of cases in dequeue.
7:42If the Queue is already empty, we cannot remove an element
7:46In this case we can simply print or throw an error,
7:49and return or exit. There will be one more special case,
7:54if the Queue has only one element. In this case,
7:58front and rear will not be -1 but they will both be
8:02equal, because we are already checking for -1 case in
8:06isempty function in the previous if. In this else if we can simply
8:10check whether front is equal to rear or not, if this is the case
8:14a dequeue will make the Queue empty, and to mark to Queue as
8:18empty, we need to set both front and rear
8:21as -1. This is what we had said, that we will
8:24would represent and empty Queue by marking both
8:28front and rear as -1. In default or normal scenario,
8:32we will simply increment front, we should really be careful
8:36about corner cases in any implementation,
8:40that's fair most of the Bugs come. Okay, so this finally is my dequeue function.
8:46In this example here at this stage, let's say be want to perform
8:49a dequeue, Queue is not empty and we do not have only one element in the Queue.
8:54So people simply increment front, before incrementing we could set the
8:58value in this cell
9:00at index 0 as something, but the value in a cell that is not part of Queue
9:05anymore
9:06doesn't really matter. At this stage it doesn't really matter what we have at
9:10index 0 or index
9:113 or any other index apart the segment between front and rear.
9:16When we will add a cell in the Queue, we will overwrite the value in that cell anyway.
9:21Let's now perform some more enqueues and dequeues.
9:24I'm enqueuing 3 and then I'm enqueuing
9:271, with each enqueue we are incrementing rear.
9:31I just performed some more enqueue here. Now let's the perform a dequeue.
9:36If I'll perform one more enqueue here, rear
9:40will be equal to the maximum index available in the array. Let's
9:43enqueue one more now at this stage, we cannot
9:46enqueue an element anymore because we cannot increment rear.
9:50Enqueue operation will fail now. There are two unused
9:54cells right now but with whatever logic we have written,
9:58we cannot use these two cells that are in the left of front
10:02in fact this is a real problem. As we will dequeue more and more,
10:06all the cells left of front index will never be used again they will simply be
10:11wasted.
10:12Can we do something to use these cells? Well,
10:16we can use the concept of a Circular array. Circlular array is an idea that we
10:20use in a lot of scenarios.
10:22The idea is very simple, as we traverse an array
10:25we can imagine that there is no end in the array, from 0 we can go to 1, from
10:301, we can go to
10:312, and finally th