😎 Stacks, Queues and Deques With Python 🌯

This post will explain the difference between 3 common programming data-structures. This post is for beginners learning python or knowledgeable programmers looking to brush up on their skills for interviews. All code examples will be written in Python.

If your learning to program you’ll inevitably come across the terms “stack”, “queue” and  “deque” but what are they and who cares? To answer these questions we must ask a higher one: What’s the importance of data structures in programming? The short answer and one you’ll probably get in a computer science class: a way of  organizing data that is stored in a computer or database. Avery true statement but I have a slightly different definition: a way of thinking about your data and selecting the right tool for the job. As programmers each of us has a giant toolbox and each new skill, idea or philosophy adds to this toolkit. You wouldn’t use a Flat head screwdriver to fit a Phillips screw so why would you use a stack data-structure so solve a problem that requires a queue? 

The Queue 

When I arrive at my favorite burrito restaurant I’m starving and  faced with a long line. There’s about 15 people in-front of me and since it would be socially unacceptable budge my fellow burrito lovers I must wait my turn. This a good example of a queue or a first in first out data structure. The patron who arrives first gets served first.

Queue image

The Code

Our burrito example:

class BurritoRestaurant:
    def __init__(self):
        self.patrons = []
        
    def no_line(self):
		#returns bool (True|False) 
        return self.patrons == []
    
    def patron_entered(self, patron):
		#python list insert method adds item at specific index
		#in our case the first index
        self.items.insert(0,patron)
        
    def patron_paid(self):
		#python pop() if passed no argument removes last element
        return self.items.pop()
    
    def line_length(self):
        return len(self.patrons)

Standard implementation

class Queue:
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        return self.items == []
    
    def enqueue(self, item):
		#python list insert method adds item at specific index
		#in our case the first index
        self.items.insert(0,item)
        
    def dequeue(self):
		#python pop() if passed no argument removes last element
        return self.items.pop()
    
    def size(self):
        return len(self.items)

The Deque

On this particular day the burrito restaurant is very busy and a few patrons who’ve been standing in the back of the line boil over with indignation and leave after seeing other patrons whom placed online orders skip ahead to the front of the line 😡. This is an example of a deque or  double-ended queue. The main difference is that new items can be added at either the font or the rear. Likewise existing items can be removed from either end. In our case patrons can be added to the front of the line or the back of the line and removed likewise.

The Code

Our burrito example:

class BurritoRestaurant:    
    def __init__(self):
        self.paterons = []
        
    def no_line(self):
        self.patrons == []
        
    def online_patron(self, patron):
        self.patrons.append(patron)
        
    def walkin_patron(self, item):
        self.patrons.insert(0,patron)
    
    def patron_paid(self):
        return self.patrons.pop()
    
    def patron_quit(self):
        return self.patrons.pop(0)
    
    def line_length(self):
        return len(self.patrons)
        

Standard implementation.

class Deque:
    
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        self.items == []
        
    def add_front(self, item):
        self.items.append(item)
        
    def add_rear(self, item):
        self.items.insert(0,item)
    
    def remove_front(self):
        return self.items.pop()
    
    def remove_rear(self):
        return self.items.pop(0)
    
    def size(self):
        return len(self.items)
        
        
        


The Stack

After my burrito was made I realized I had forgotten my wallet and had no “stacks 💵 😉”. As punishment for my crime and for restitution I had to wash dishes. After I washed them I stacked them for the customers. When the customers came to take a dish they took it from the top each time.

Picture of a stack

Sometimes called last in first out. Newer items are near the top while older items are near the bottom.

The code

Our burrito example:

class Dishes:
    def __init__(self):
        self.dishes = []
    
    def no_dishes(self):
        return self.dishes == []
    
    def add_dish(self,  dish):
		#add to end of list
        self.dishes.append(dish)
        
    def take_dish(self):
		#remove from end of list
        return self.dishes.pop()
    
    def current_dish(self):
		#grab current dish up for taking
        return self.dishes[len(self.dishes) - 1]
    
    def total_dishes(self):
        return len(self.dishes)
    

Standard implementation

class Stack:
    def __init__(self):
        self.items = []
    
    def is_empty(self):
        return self.items == []
    
    def push(self, item):
        self.items.append(item)
        
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[len(self.items) - 1]
    
    def size(self):
        return len(self.items)
    
        

I hope this post had made clear the difference between 3 common programming data structures and you have more tools to add to your tool-kit.

1 thought on “😎 Stacks, Queues and Deques With Python 🌯

  1. Hi Tyler.
    I found you though the Star Trib article, “Platform helps push growth,” read today.

    I have a need for an international contract management application like “Contract builder with Olio Engine” that you and Dan Nelson are working on. My need is for a project based learning application. It’s for home based B2C block parties channeling K-12 Kids’ Ideas in ways to solve elementary engineering problems, shared globally, providing parents’ income. Hope to launch first in rural USA then scale in rural China. See website: https://www.ToadSquareKids.com

    Can we meet to explore my plan with your plans? Thanks.
    Fred
    Fred@CrossLinkStructures.com
    612-209-5526

Leave a Reply

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