In the previous couple lectures, we explored the stack ADT and the List ADT before that. The List ADT is very flexible and allows insertion and removal from anywhere in the list. The stack ADT on the other hand, is very restrictive and allows only insertion called pushing and removal called popping at one location in the stack, that is, the top of the stack. A stack is therefore, a last in, first out or LIFO data structure. In this lecture we explore a first in, first out or FIFO data structure, the Queue. For Americans, we usually refer to the places we wait to buy groceries or tickets or at a cafeteria as lines, but in British English speaking countries, the term queue is actually more common. You might say you were waiting in queue to make a purchase. In pretty much all English speaking countries, the concept of a printer queue might be reasonably familiar to those with a technical background. People send their print jobs to a shared printer and these jobs wait in a queue to be printed. Obviously before we write any full implementations, we need to write out the interface for the queue ADT. Then we'll work on an interesting array based implementation. First, let's create the project called ArrayQueueApp. I have the project name ready here and a good location for it. We will hit 'Create.' And of course, we need to create our files to be prepared. So, let's just create all three that we are going to need for this Visual Studio project. So I'm going to create the main.cpp of course. And then I will also create the Queue.h which will hold the abstract data type or the interface. And then of course, the ArrayQueue which will hold the actual implementation with an array based backing data structure. AlI right. I'll go into main and I will put iostream and also just to be ready, I will include ArrayQueue.h. First things first, let's go into Queue and put the include guards. All right, public, virtual void enqueue. Now these are a little weird to spell so pay very close attention. So enqueue, it's just e-n followed by the name of the data structure or abstract data type queue, q-u-e-u-e. So, it's kind of a strange word. dequeue() so that one right there, d-e-q-u-e-u-e. So, that has to do with removal peekFront(), that's const because it just looks at the front. isEmpty() and makeempty. So, isEmpty is const, peekFront is const, and then the other ones,  that extra should be  capilalized  right there, the other one's are not because they make changes to the actual Queue. So now of course, we want to create an array based implementation in ArrayQueue.h. However, this one is going to be a little bit different from what you might expect. Unlike the stack, the queue has two openings: the front or head of the queue and the back or rear of the queue. Adding an element to the queue will be done by enqueuing it to the back of the queue, just like it you would get in line at the back of the line. When an element leaves the queue, it will do so by dequeuing from the front of the queue. If we designate index zero in the array  as the front and also the back at the beginning, when elements are added to the queue, the back will grow to higher indices in the array and as elements are removed from the queue then the front will grow to higher indices. They'll scoot over. The problem is that the back and the front keep inching over to the end of the array and they'll finally meet. We will have all this unused space at the front of the array but we can't use it in this setup. It'll appear like it's full. The time honored solution is to basically pretend that the array is a circle. That is the end of the array will wrap back around to the front of the array. So when the back, it gets to the actual end of the array, for example, we can use a modulus operator such as backIndex = (backndex+1) % length and this will of course cause the back to wrap around the array and its actual index will be before the front in some cases. However, this does cause a potential problem. We must be able to detect the difference between an actually full Queue that is all the elements of our array occupied, all the cells are occupied with elements and an empty queue. In both cases, the frontIndex = backIndex+1. So, how are we actually going to solve this problem? There are multiple solutions to the problem. One would be to track the number of elements added to the queue and then if the number of elements is zero, we know that the queue is empty when frontIndex = BackIndex+1. Another solution involves sacrificing one of the cells in the array to act as padding between frontindex and backindex as they move around the queue. These two are a couple of perfectly good implementations. There's always a little bit of extra memory being used but both work. We are going to implement the version of the circular queue with the counter. This means when the queue dequeues or enqueues we have to remember to keep track of the number of elements left. So, let's implement ArrayQueue.h and test it out in main.cpp. Over here in ArrayQueue, we're going to of course do the include guards. All right. In here, we have to include iostream and of course the interface, a pure abstract class here. ArrayQueue inherits publicly from the Queue interface here. We also have public and then we will of course have private. And the private section has a few things that we are going to need. It's a little bit different from what we've done before. Now, we still need an mArray that we can dynamically create and of course MAX_SIZE and we're going to have the numElements. But what about a pointer which will be in the linked implementation or an index in our case here, we will actually have to maintain two of them, not just one. So, front and back. So we need both of those. All right. So now, for the constructor, ArrayQueue, size by default is 16 and we can initialize MAX_SIZE to that. The front and the back are set to zero to start off with. And numElements  =  0 in this case. And then also we need a virtual ~ArrayQueue(), destructor will delete the mArray and then enqueue the new entry, we will have that ready and then dequeue. For enqueue, we're going to say if (numElements < MAX_SIZE -1) then set mArray[back] = newEntry; and then back = (back +1) % MAX_SIZE; and then of course numElements++. Otherwise, if there's not enough room, we'll say, "You cannot enqueue onto a full queue." There we go. dequeue, on the other hand, equals zero if not isEmpty, data = mArray[front].  Oops that  didn't  work. Front. There we go. We progress the front now with of course wrap around technique. All right. If it is empty though, we do at least want to set the data to something that I guess isn't necessary because it's already set to zero. So we'll just print out an error. You cannot dequeue on an empty queue. And then of course we can return the data, not return zero, return data. Awesome. Now, of course we have peak front and it's going to be in some ways similar to dequeue but it's non-destructive. We have the isEmpty and of course an else for the else we'll just say queue is empty. You cannot peak the front and let's do this and data equals zero. And of course at the very bottom we return data and then if it's not empty we set data equal to mArray at front. Right there. Pretty cool. There's no movement of the indices because we're not changing the front, then we have is empty and we're going to return numElements equal to zero. Okay.

So, in this case since we're using the counter, we don't have to do any kind of magic with the front and back of the queue in order to determine whether it's empty or not. So, we just used the number of elements to help us. To make it empty, we basically set it to the same thing that it was at the beginning. Right.

So, for this situation what we're going to do is we're going to just say front equal zero, back equal zero, and then num elements equal zero. Perfect. Now, we probably want to test this out in main. So, in main what we're gonna do is we're going to create a queue, just call it queue. Let's start with one, in this case we don't, really doesn't really matter. And we'll go to i <= 16. So, we'll take the queue and we'll call it enqueue (i * 100). There you go. And then maybe outside the loop. Well enqueue(1234) to see what that does. And then while not queue.IsEmpty. Well it's not empty. We just print out queue.dequeue. Great. Now, we'll also try queue.dequeue again. Then we'll do some alternating to test the circular capabilities just to make sure that we're getting good functionality. So, we'll call this circular test. So, this will keep pushing everything over int  i  =0;  i<20; in this case. And this time we'll just say well let me see here. I guess we do that just enqueued and then we'll say i 20 or times 10 rather. And we're going to actually enqueue it items 10 and now what we're gonna do is something kind of interesting, we're going to say i % 3 == 0). If that's the case then we're going to do some dequeuing. So, just to kind of add a little bit more variety to what we're testing and then that's the end of that for loop. In the wild loop up here and then down here we're just going to do queue.enqueue(123), queue.enqueue(234), and then queue.enqueue(345). Perfect, perfect, perfect. And of course let's run it, build it, make sure there aren't any errors. Looks like it succeeded. So, we're going to start without debugging and you'll notice, it looks like we're getting a measure of lots of fullness here, so it looks like there might be something wrong with our implementation here. Okay, so it's probably in the enqueue and dequeue process, so let's go over here. Well, did it again, there you go.

So, that should be modulers, not end because that'll do bit wise and on this and not give us the result we expect. So, make sure that this is a modules and this is a modules for both your enqueue and your dequeue. Let's build it see if that was the only problem and it looks like it. So, you'll notice the elements are being printed out or dequeue in the same order that we enqueue them. Which is what we expect. And then we tried dequeue an empty queue afterwards and then we do our little circular test. So, we enqueued, dequeued, enqueued, enqueued, enqueued, dequeued, enqueued, enqueued, enqueued, dequeued. So, it's just to do some tests. So, we enqueued 10 then a 20, 30 and then the 10 gets to leave first, then a 40, 50, 60 then the 20 gets to leave because it was second in line. Then the 30 gets to leave after some more enqueuing, then the 40. So, it's expected. It's the exact expected output that we desire. Perfect. Perfect, Perfect, awesome job. So, we can see a bunch of the behavior that we expect from our queue. And that is in fact wrapping around properly.

Also before moving on I have a really really short challenge for you. For this one, it's more of a theory practice situation. So, all you have to do is answer the following questions. What does LIFO mean? What does it stand for? What ADT exemplifies LIFO? What does FIFO mean? What ADT exemplifies FIFO? So, pause the video and try to answer these questions as best you can, come back when you're done or if you need some help. Did you remember what LIFO and FIFO mean and which ADTs correspond to each? Well, here's the answer LIFO means last in first out and is exemplified by the stack ADT. FIFO means first in first out and is exemplified by the queue ADT. Great job. In the next lecture, you'll have a chance to work on your first project for this section. I'm excited to see if you can use what you've learned in this section and apply it to this first project. I'll see you there.