Data Structures — Queue

Last time we discussed Stack and now we have it’s sibling, Queue. Instead of being Last in First Out, a Queue is First in First Out (FIFO). You can imagine this to be similar to a line of people in the post office all queued up. With no cutting!

Queue has similar methods to that of Stack, and the names are changed to reflect the difference in order: size, peek, enqueue, and dequeue. Enqueue is getting in line, and dequeue is removal from the line.

The key thing to remember with Stack vs. Queue — in a stack you eat that last pancake first (see prior blog on Stack), so your length is corresponding to the current value to return and will continue to do so each time you remove one. Whereas in Queue, your first most item is what you’re tracking, no matter how many items you add to Queue you want to return that first one. And when you take the first person out of the post office line, the length no longer corresponds to the correct position. If you have 5 people in line, and you serve customer 1, (or zeroth customer, you CS lovelies) how are you going to serve the next person? By tracking the front and end locations.

TLDR; Constructor in Stack’s pseudoclassical constructor tracks only storage and size variables, in the Queue constructor — it uses a front and back variable. It’s important to manually update the pointer to which to return next, if you think of it like a linked list’s node.