Tuesday, October 15, 2024
Coding STEM

Queue and Stack Data Structures — Explained

Hi visitors! This post is about explaining the very essential data structures such as Queue and Stacks in a simple way, and provide you with some animations to help. Then I’ll explain how you can implement either data structures in a real-world situation using Python (or any other language, once you understand these fundamentals).

I won’t go too much into explaining the basics of what a queue or stack is here as you can easily search online and get their definitions and details on your own. What I’ll do here though is take that basic understanding and explain them visually as well as their applications in the real-world.

Just to recap, a Queue is a data structure where items contained in it are FIFO, meaning: first-in, first-out. The first time that was added to the container Queue must be removed first. Then the second and so on. If we don’t do it that way, that will NOT be a Queue in the standard sense. (There are variations used in the real-world such as priority queue, which takes both chronology and urgency into deciding what goes first…but the concept is the same).

Real-world usages of queue include: ticket purchases, anything that works in first-come, first-serve model such as producer->consumer (e.g. customer service, latest data consumption via API…weather, stocks, tickets, etc.).

I created the following clip to show how customers are lining up to a kiosk to purchase tickets for a show or ride.

Queue video: Queue visualized

Queue

To your left (left side of of the kiosk where the line forms) is the queue at a given time. First there were several customers, and as each is served, the customer moves past the kiosk, and that person is removed from the line, that is, from the queue. The line is the queue in this case.

Stack is LIFO, meaning: last-in, first-out. It’s a data structure where the last or latest items are removed first. Then the one that arrived previous to that time is removed, and so on. Ultimately, the very first item is removed last.

Real-world usages of stack include: Undos (ctrl-z on Windows), Browser history navigation (last one visited is at the top, first one visited in the session is at bottom).

Below is a clip I made to visualize a stack of browsed sites. If we visited site A, then B, then C. And then we pressed Back in the browser, it should go to site B. If we press Back again, it should go to site A. Each Back command can be analogous to a pop function (removing an item from the stack). In today’s browsers, we also have Forward command, so you can navigate back and forth in a circle forever…that’s still can be done using stack, only thing you have to do is when you pop the item on Back, you save the item you popped and insert them (push or append) back into the stack! And then when you press Forward when you’re at the top of the stack (e.g. at very first visited site A), it goes to the next item (e.g. site B), and Forward again, it goes to site C. Try it on a piece of paper the push (append in Python) and pop, remembering append always adds an item to the last position (imagine tail end or bottom of stack) and pop or removes the item from the last or top position!

Let’s not get ahead of ourselves though, let’s not worry about the Forward and circular links yet, let’s first grasp the basic stack concept.

Stack video: Stack visualized

Stack

Now that you understand the basics of them, let’s talk about how to implement both using Python. You can do it in any of your favorite languages however. In Python a queue data structure is called: deque (from collections module). In Java, it’s called LinkedList. e.g. Queue q = new LinkedList<>(); Then q.add(), q.remove() for items manipulations. In C++, it’s called std::queue. e.g. std::queue q; q.push(), q.pop()

Let’s get back to Python…you’ll see that in Python we can choose to add an item to the data structures either at end (as it is by nature for Stack implementation) or to the very first position (as it is useful for Queue implementation).

The first thing you need to know is deque. This class, unique to Python, makes it possible to create deque objects that are very efficient for implementating both Stack and Queue data structures in your programs. It’s flexibilty comes from the fact that it allows inserting items at the very first position of a structure or the very last. And since Queue is opposite of Stack, we can implement Queue by adding new items at last positions and removing the first…this is done by appendleft() method of deque.

The Stack then can be implemented by adding items using append() method which adds new items to the ‘right’ or top of the stack.

A “push” action typically means to add an item at end, but there’s no push() method in deque. Instead, we use deque.append(x) for stack implementation and use deque.appendleft(x) for queue. A “pop” action means to remove an item. Fortunately, there’s a deque.pop() method in Python. So, for items in a Stack, pop() removes the latest item (e.g. top most dirty dish in the stack) first. And in a Queue data structure, pop() removes the first item (e.g. right-most item in line).

How to use the deque Class and create our own deque objects

deque module is included in the collections library of Python, so we need to explicitly import it as below:

import collections
from collections import deque

Let’s start with Queue implementation, then we’ll go into Stack.

To code the Queue animation you saw above, you first create a deque object, then add the customers: Bob, Jen, Megan, Bill.

q=deque() # create an empty deque object
q.appendleft('Bob') # Bob was the first customer
q.appendleft('Jen') # Jen was second customer
q.appendleft('Megan') 
q.appendleft('Bill') # Bill was last customer in queue

Next, you can put a timer to simulate the ticket being sold, paid for, cooking, preparations, serving, etc…whatever the service Bob came for. Next, when he’s served, you simply update the queue by popping him out with:

customer_served=q.pop() 
# Verify...
print("customer served:", customer_served)
print("Latest queue (customers waiting):", q) 

You’ll see that now Bob is no longer in line, and queue contains: Jen, Megan, Bill. A bit of caution however, if you pop() from a queue when it has no item, you’ll get an exception/error and your program will halt! To avoid it, you can wrap all actions in try:except block (another discussion/post) or check before popping with:

if len(q)> 0:
    customer_served=q.pop() 
    ...do other stuff
else:
    print("No more customers waiting.")

That wasn’t hard at all. In real applications though we’ll have to deal with much more complex data structures even within the queue itself. Just to give you a glimpse…imagine your app needs to keep track of which customer ordered what item(s), their prices, time of order, and of course the order of the order, much like a fast-food restaurant serves its patrons all the time! Behind it, is software running written by real programmers that makes everything run smoothly and makes possible the necessary analytics for franchisee and franchisors or HQ!

A data structure like this can be implemented using a queue of dictionary objects as below:

q.appendleft({
    'customer':'Bob',
    'timestamp':'05/25/2022-08:12',
    'item':'latte',
    'price':3.95,
    'size': '12oz'
              })

q.appendleft({
    'customer':'Megan',
    'timestamp':'05/25/2022-10:15',
    'item':'mocha',
    'price':4.95,
    'size':'16oz'
              })

and so on...

Therefore, we can get the name and type of order for, say, the second customer by this:

q[1]['customer'], q[1]['item'], q[1]['price']
# because index is 0-based in Python

To show all orders in queue, you can do:

for i in range(len(q)):
    print(q[i]['customer'], "\t", q[i]['item'], q[i]['price'], q[i]['timestamp'])

To see remaining customers’ in line, you can do:

for i in range(len(q)):
    print("Customer(s) still in waiting...", end='') 
    print(q[i]['customer']) # out: Customer still in waiting...Megan

To get info on which customer got served, do this:

served=q.pop() 
print("Just served details:", served)

And so on. It’s beautiful, isn’t it?

Let’s move on to Stack implementation now!

In the Stack video clip above, you should use stack.append() instead of appendleft() as was used in my queue code. As before, first you create a deque object, and then you add the items.

stack= deque()
stack.append('http://flyingsalmon.net')
stack.append('https://zeno.fm/radio/flyingsalmon/')
stack.append('https://duckduckgo.com/') 
stack.append('https://www.youtube.com/')

To simulate a Back button action by user, you do:

site=stack.pop()
print("Site popped:", site)
print("Latest stack:", stack) 

Call the above code block everytime user clicks Back for example. And it just works. Again, be sure to check len(stack) before trying to pop or you’ll get exception!

Another real-world application might be user-action undo. Such as, cut, paste, delete, move, etc. We need the action and the system object being acted on (e.g. file or folder). So, it might look like this:

stack.append({
    'action':'cut',
    'file':'abc.txt'
              })

stack.append({
    'action':'paste',
    'file':'abc.txt'
              })

stack.append({
    'action':'delete',
    'file':'def.txt'
              })
... and so on

To catch exception, you can do this:

try:
    undone=stack.pop()
    print("Last action UNDONE:", undone) # there is NO item 4...so onto except block    
except:
    print("No more to undo.") 

print(stack)

There you have it…so critical, yet so fun to play with. I hope you’ll have fun it…create your own scenarios and data structures and the more you practice the more you’ll get comfortable with it. Enjoy.



Interested in creating programmable, cool electronic gadgets? Give my newest book on Arduino a try: Hello Arduino!

Leave a Reply

Your email address will not be published. Required fields are marked *

Back To Top
+