In the previous lecture, you learned about the ADT Queue, wrote an interface for the Queue, and also an array-based implementation, the ArrayQueue. You probably saw a pattern in the previous lectures, alternating between array-based and linked chain-based implementations. So, where is the implementation for the Linked version of the Queue?

I'm glad you asked, because you're going to be writing it. Using what you know about linked chains at this point, and what you know about the Queue ADT, you're going to implement a link-based Queue. Create a project called LinkedQueueProject. Make sure to copy over the Queue interface we made before and write a LinkedQueue class, LinkedQueue.h, that inherits from the Queue class. Also, make sure to write a main function to test out the code or you can copy over the main function from the other project.

As a hint, we used two variables to hold the indices for the array-based implementation of the queue. So, you might consider using two pointers this time to represent the front and the back of this linked implementation. And, you might also consider changing the structure of the node itself a bit. You can copy over the node from other linked implementations but make the node have two pointers, two next, and also previous. This will allow us to create a double-linked chain, and that will make the process much easier. Don't forget the corresponding methods either. All right, just to give you an idea of what this is going to look like when it's run, we're going to go to debug, start without debugging, and it should look like pretty much what you expect. And the same thing that it had when we had the array-based Queue as well. All right, hope that helps. So, pause the video and give this project your best shot. Come back when you're done or if you need some help.

How did that go for you? Were you able to complete this project? This one may have been pretty challenging. You could use the previously written code in the linked-based implementations of the List and Stack to help guide you, but this implementation was very unique in that you need to track the front and the back of the queue and had a modified node structure as well. Let's work on it together. We'll just use the main.cpp from the array-based project we worked on before. This will be a good test because other than changing the class type and the includes, the actual behavior of the List from the user's perspective should be pretty much the same, right? So, I've done a little bit of the legwork to start out. I have Queue.h already copied over and then also I did the right click 'Add Existing Item' and added the linked or added rather the Queue.h and also the main.cpp. I've changed the include for main.cpp and we have to change the data type here to LinkedQueue from ArrayQueue and make sure that works. And then, what we're going to do, let's make sure this isn't a problem, LinkedQueue. So, it says it's abstract. We haven't implemented the method yet, so it's going to be angry. I have the skeleton of the LinkedQueue right here. It's not filled in yet. It just has LinkedQueue inherits from PublicQueue. So, as far as this is concerned, the reason we're getting an error is it thinks that we're just leaving it unimplemented. So, once we implement it, this error will go away.

Now, let's look at our node which I copied over from the linked list implementation, you can copy it over from the LinkedList implementation or the LinkedStack implementation. And there's only a couple little modifications we need to make. Notice again this is in LinkedQueue.h. So, the only things we really need to do is inside the node constructor, we need to have previous there. We need to actually add previous to the private section as well. So, we can double link it and add that. This previous equals the previous parameter. And then, of course, we want to also add the getPrevious, and that'll just return previous. And also setPrevious, which will just set previous if we need to reset it or something like that. So, it's mostly for consistency. We don't use all of these methods but for consistency with the other implementations. The other things that we need to do right here, we have a constructor, of course, that we'll need to implement. But first, let's add the public section and also a private section. I think for the private section, we need to have the front and the back. So, front and also node pointer back or rear, whichever you prefer. So, we have LinkedQueue and we set front equal to null pointer and back equal to null pointer as well. And of course, we have a destructor that would be useful. And this is just going call makeEmpty. All right, moving on to some of the more slightly complex or more complex methods... enqueue. First, we create the new node, regardless we say equals newNode, and if we're enqueuing, we have the newEntry being added and the back is the, if we look over-- sorry, not newNode, new Node. The newEntry if we look at the node implementation up here, the second argument is next and the third argument is previous. So, the second argument, next. So, since we're adding it to the back, this is going to become the new back because we're enquing, right? So, the back and then we set the previous to null pointer because we're going to be the absolute back of this entire chain. So, that's the current back that we are now pointing to as our next. And then if it's the first node, meaning if the Queue is empty, it means it's the first node, then we set front = newNode, because the back and the front will match. If it's not empty, the last node sets its new next to the newNode before being replaced as the back node in just a moment. So, back we setNext equal to this newNode. So, if it's not empty, the back now has its next pointing to the newNode. And then, right here, the back becomes the newNode. So, regardless of whether the chain was empty or not, we always make the back the newNode, right?

That becomes the new back. That's the end of enqueue. The next thing up is going to be dequeue. All right, so int data = 0, and then we're going to return zero or return data, sorry, return data. And if this time, if it's not empty, then that's valid. Otherwise, we have to print out, "Hey, you can't dequeue from an empty queue", right? So, if it's not empty, that means we have the tempToRemove is going to be the front, right? So, because we want to remove the front but we don't want to lose the rest of the chain. So, we have to do a little bit of manipulation here. So, we point to that node at the front that's currently the front, we grab the data from the front to getData, and now the front variable itself is going to hold a new address because we're calling the current or what will be the old front's getNext. So, now front has been replaced by a new front, and now this thing is just dangling off in the universe as attempt to remove that was the previous front but we have to delete it. tempToRemove, so we delete that. Once that happens, if the front is null pointer, then we have to set the back equal to null pointer as well because we want them to match. Otherwise, if the front is not null pointer, we set front's previous to null pointer because it's at the very beginning and it doesn't have anything in front of it. So, it's previous is set to null pointer. All right, pretty good.

The next thing we need to do peekFront, and I guess just as a node, I guess people could design this. So, the front is pointing to the next and the back is pointing to the previous. It just depends on what direction you want your queue pointing. But either way, if you format it correctly it will still end up working. So, peekFront data is zero. If not isEmpty, the data is going to be set to the front's... data. Otherwise, we're going to print out something for the user, "You cannot peek the front of an empty queue," and again, you might consider maybe upgrading all these to have exception handling. So, this one's peak front, this one's dequeue, and they're down a little bit. And now, it's pretty much the home stretch here, isEmpty is not hard. We just return is the front equal to the back, right? And then makeEmpty, while it's not empty, we just call dequeue. Since dequeue already takes care of the removal of the nodes right here, the deletion of the nodes and setting the back and front to null pointer as needed, then we just call it here, perfect. Now over here in main, I just copied over all the code and then did the slight modification of changing it to a LinkedQueue here and there from the array-based Queue. And it should function the same as the array-based Queue, so let's run it. All right, build... and now run, and it's pretty much what you expect. You get a bunch of dequeuing and queuing, dequeuing and queuing, testing, testing, testing. Everything seems to be working quite well. Amazing, so it's totally okay if you struggled with this one. This one was pretty significant. I think if you were very careful and really thought about the design, you probably came up with something close to what I did. But don't feel bad if you weren't able to solve this one or came up with a different solution. It required you to really think about what a double-linked chain would look like with pointers to previous and next. Maybe you swapped those and you had to manage all of that well to get any of this to working properly. So, it's totally okay if you struggled or had any kind of problems. But awesome work, everyone. In the next lecture, we'll check out another project involving data structures. I'll see you there.