Okay, next, we'll briefly consider queue implementations using the same basic underlying data structures. So, here is the corresponding API for queue of strings. Actually you know it's the same API for stacks just the names are different. Instead of push we have enqueue instead of pop, we have dequeue. And the semantics is different. For enqueue we add an item say at the end of the queue and for dequeue we remove an item from the beginning. It's as if you're waiting in line to buy a ticket. When you're enqueue you're at the end and when that's been in there the longest is the one that comes off. So let's look at how we implement those first using linked list and then arrays. So, now our representation of a queue with the linked list, we need to maintain two pointers references. One to the first item in the list and the other to the last item in the list. When we insert we're going to add the item at the end of the list instead of the beginning and when we remove we'll do the same and we'll take it off the front. So here's the implementation of dequeue. It's identical to the code for pop for a stack. We save away the item. We delete the first note by advancing the reference and then we return the item, so identical. To add a node or enqueue, add a new node to a linked list, we want to put it at the end so that would be the last one return. So we, to add it at the end so first thing we need to is save a link to the last node. We're going to need that because we need to change its reference from null to point to the new node. Then we'll create a new note for the end of the list will populate its fields and then that old link will change that from null to a pointer to the new node. So again just a few lines of code. That's basic linked list processing. Actually years ago when we taught courses in algorithms and data structures much of the course would be about this kind of pointer manipulation but nowadays that's restricted to just a few implementations like stack and queue and a few other fundamental data structures. So we don't need so much anymore general programs for manipulating linked list. We encapsulate them in basic data types like these. Alright, so let's go back to our full implementation and this is just taking care of collecting a curve from the previous slides but also taking care of special cases when the queue is empty to make sure that if the queue is empty after we remove an item, we're going to last at null and make sure that both first and last always are what we want them to be. So those are details that are easy to check. Okay, what about arrays? Well, we want to do the details but it's not difficult to implement queues with resizing arrays as well and not difficult but definitely a tricky programming exercise that people are welcome to try. So we'll maintain two pointers. The first item in the queue and the tail which is the position for the next item to appear so for enqueue you add a new item at tail and for dequeue you remove an item for head. And the trick is that once you get past the capacity, you have to reset back to zero and so that's a little extra code and then you have to add the resizing capability as well to implement data structure the same as for stack. And we'll leave that as an exercise.