‫So now we're going to look at cues.
‫And a cue is just like when you stand in line, you can add items to the queue and then you can remove
‫items from the queue.
‫We saw with a stack that a stack is litho last in, first out a queue is FIFO, first in, first out.
‫So with our queue, we're going to write a function that is called in queue which adds items to the
‫queue.
‫And then we'll write another function called DX queue, which removes items from the queue.
‫So just like we did with stacks, we're going to look at two different data structures that we could
‫use for implementing our queue.
‫So we're going to start with a vector.
‫And as we discussed before, on this end of the vector, removing and adding are both O of one.
‫But at this end of the vector, removing and adding are both o of RN.
‫So with the queue we have to add from one end and remove from the other.
‫So if we add from this end and we remove from this end, we have one that is O of N and the other that
‫is of one.
‫And likewise, if we add from this end and remove from this end, it's the same thing.
‫One of them is O of one and the other is O of PN.
‫Now let's compare this to a linked list with the linked list.
‫If you remove from this end, it's O of n, and if you add its o of one and on the other end, removing
‫as o of one and adding an item is o of one.
‫So if you're going to implement a queue with the length list you don't want to remove from this end,
‫what you want to do is in queue from this end and D queue from this end and they're both O of one.
‫And since you can do both of these as of one, a linked list is always going to be more efficient for
‫implementing a queue than a vector.
‫So that is the way we are going to implement our queue.
‫So with a linked list, we had head and tail and a queue.
‫We're going to call these first and last and that is our quick introduction.
‫To accuse.