A queue is a first-in first-out data structure similar to waiting in line. We'll represent a queue visually by having a array or list or any type of container inside of a series of lines. We'll see an enter point and an exit point. So, you can imagine, if you're waiting in line for a cup of coffee, the first person who arrive in the line will get their drink first. People arrive at the back of the line and move through the line in the order which they arrived. This kind of model we'll model with a queue. When we talk about data structures, we'll always talk about a data structure in terms of their abstract data type or how data interacts with the data structure without talking about an implementation. So, an ADT is not an implementation, but it's a description of what the data structure does. Then, we'll explore the implementation after knowing the description. The abstract data type for a queue is going to have four different functions. The first is, we need to be able to create a queue, and that will create an empty queue with nothing in it. We need to push data into the queue, and that will add data to the back of the queue. When we want to remove data from the queue, we'll pop the queue. Popping the queue will take the first element of the data and bring it out. Finally, we need some ability to determine whether or not the queue is empty or not. The empty functionality will determine if the queue has anything in it or is completely empty. So, let's consider a simple operation on a queue thinking only about the abstract data type and what we know about how a queue functions. We first are going to create a queue of integers. So, we'll go ahead and initialize this queue, and we know it's going to contain integers. We'll go ahead and push the number 4 onto the queue. So, add four. Four is ready to be the first person off the queue. The second thing we'll do is, we'll push number 2 to the queue. Then, finally, we'll pop a number from the queue because the queue is going to take the first thing to arrive. Four is going to get popped off the queue, removed from the queue, and now, two is next element to be removed. In C++, we actually have a queue provided for us by the standard library. This is an std queue. Similar to a standard vector, we can use a standard queue by doing st queue. It's a template type. So, here, we have a queue of strings. Here, I'm going to in queue three different elements by saying, push Orange, push Blue, and push Illinois. We expect Orange to be first. Behind Orange is Blue, and behind Blue is Illinois. On line 21, we see out the first pop. So, we get the queue at the first element, so we expect this to print out Orange. Since Orange has been popped off the top of the queue, we now go to the next line, line 25. We add Illinois to the queue, we see the enter here is at the end of the queue. We'll add Illini, not Illinois. Then, we do st second pop is queued up front. So, what's to the front of the queue now? It is Blue. So, the output of this program, understanding our queue, is that after adding three elements, when we pop off an element, the element should be Orange. After adding Illini, we pop off another element, and it should be Blue. Let's see if this logic matches it when we run the implementation. Moving into the queue directory, running make, and dot slash main. The first pop is Orange, exactly what we expect. The second pop was Blue, exactly what we expect. So, our logic and the code matches up. But let's actually understand what the queue does internally and how fast it runs. Internally, a queue can be implemented with either of our two basic data types that we've already discussed. We can have an array-based queue or a linked list based queue. In an array-based queue, an array's going to sit in the queue and will have an index for each element in the array. The array will be initial size. Again, we can expand it by doubling the size or shrinking it by halving the size as we need to. When an element arrives in the queue, we'll simply add it to the queue. We can continue to add items to the queue as they arrive. We only need to ensure that the elements as they arrive is placed further back in the queue than all of the elements that currently exist. In this array-based queue, notice that we can always have a counter to this term in the index where we should enter things next. We can always keep track of the index. For example, here, we might be at index eight of where we should be removing from the queue. There's a number of different ways to set up the arrays, but so long as you keep track of where the insertion point is and where the removal point is or where the pop and push points are, we can always just adjust them by adding one or subtracting one and resizing the array as needed. All of these operations are just operation of indices and are always going to run in O of one time. A list implementation is slightly different. We are going to have a linked list, and we know in a linked list, we can insert at front in O of one time. By inserting at front in O of one time, we can continually add things ahead as they arrive into our list. What we absolutely don't want to do is to have to traverse through the entire list. Instead, what we want to do is, we want to store a new pointer called a tail pointer that's maintained the very end of the list. This tail pointer will allow us to always access the last element of list, and it's something we can easily maintain. The last thing that we need to do to maintain this tail pointer is, in links memory, instead of just linking our memory forward, let's make sure we link all of our memory backwards as well. So, if we do this, whenever a new element arrives, we can always add it directly to the head. We know that adding to the head takes O of one time. On the other side, when we have a tail pointer, we can always find the element at the very end in O of one time. We can remove this element and update the tail pointer to the previous element if we have this doubly-linked lists where we have back pointers. So, our update also takes O of one time if we're careful with the design. So, using a base idea of a list, we can implement a list by adding a few minor features and get an O of one time for both push and pop onto a list, just like we were able to with an array. So, summarizing all of this, creating a queue data structure is going to take O of one time to create empty array and O of one time to create empty linked list. We argue that push and pop were both O of one time, so long as we have a doubly linked list for a linked list and so long as we do an intelligent resize, where we're doubling the size every time we run out of room in our array. Notice that we have O of one operations in the array because we're always inserting it at the front of the array and removing from the back of the array. Finally, we can determine what the size of each of these components are in O of one time. So, when we're building a queue, every operation we perform on a queue is an O of one time operation. That means it doesn't matter if we have a million things in the queue or just one thing in the queue. By using a queue, we guarantee there's going to be a constant run time, no matter how large the queue grows. So, a queue is a first-in first-out data structure that mimics waiting in a line. A queue may be implemented with either array or a linked list. By using wise implementation for both of these structures, we can build a queue that runs in constant O of one time. This is going to be a powerful data structure that we're going to use to manage a lot of things as we go forward in this class. The sister data structure to the queue is the stack. I'll talk about that one in the next video. I'll see you there.
