Queues and Stacks
A quick debriefing on FIFO and LIFO
Greetings, one and all! With the holiday season upon us, it’s easy to find ourselves feeling festive, joy, and generous. In fact, the holiday season is a perfect time to show love and appreciation with gift giving. And, I couldn’t think of a better gift to myself than continuing study of data structures! This week, I got into the topics of queues and stacks — what they are and how they’re different. If you’re up for some holiday fun yourself, read along!
Overview
Queues and stacks are linear data structures in which elements can be added or deleted. Nice! This sounds pretty similar to an array, right? For demonstration purposes, I will be using arrays in the examples. Great! Now that we know what they are and how they’re similar, let’s see how they’re different.
Queues
As stated, queues linearly store data, but they follow a directional pattern or rule for how elements are added or deleted. In a queue, elements are added(enqueued) to the end and removed(dequeued) from the front. In other words, queues operate using the First In, First Out(FIFO) principle. This is a lot like a regular line in which the first person in line is the first person served, and like wise, the last person added to the line is the last person served.
For example, let’s think of a deli or bakery counter. There’s a little pull tab machine that dispenses numbered tickets in numerical order. There is also a digital screen(or yelling employee) that counts up the numbers so that customers can be helped in the order in which they arrived(FIFO). In code, it could look something like this.
To see it in action, let’s add some customer numbers to the line.
Once a customer has been served, we can simply run the beenServed function to remove them from the line.
Stacks
Stacks linearly store data, and also follow a directional pattern or rule for how elements are added or deleted. Unlike queues, stacks both add and delete elements from the front. Meaning, the last in is added to the front and is also the first to be deleted. Simply put, stacks operate using the Last In, First Out(LIFO) principle.
A good example is to picture trays in a cafeteria. After eating, trays are left in a designated tray spot. When a diner is finished eating, they bring their tray to the spot and set it on top of the tray stack. The last used tray(latest element) is added to the top. When going to remove trays, assuming one at a time, we’d have to start with the top and work our way down(LIFO).
In code, it could look something like this.
Assuming each tray has a different color, let’s add some trays and see it in action.
When it comes time to clean up, let’s remove trays by running the removeTray function.
Conclusion
Queues and stacks are both really useful ways to store, add, and remove data. The main point of concern is how and in what order data is added and removed. Queues — First In, First Out — think of a stereotypical line: first in line is served first, others fall in after the person at the end of the line, and last is served last. Stacks — Last In, First Out— think of a stack of books: new books will be added to the top, and to get the book on the bottom, the top ones need to be removed first.
As always, research and experiment with these on your own. Happy Coding!
