STACKS AND QUEUES IN PYTHON

Stacks and Queues are abstract data types (ADT). These widely used data structures are implemented in applications from clipboards to web browsers and computers memory, to list a few. Stacks are similar to arrays, lists, and linked lists, push(add) and pop(remove) operations of stacks and queues are the main operations of the data structures. Stacks and Queues are linear data structures implemented in opposites.

In this article, I will be taking you through implementing stacks using the collections.deque module and creating custom stacks and queues.

How do stacks and queues work?

The stack is implemented such that operations are caried out in a method known as the LIFO (last in, first out).

Say we have a deck of cards numbered and sorted ranging from 1 to 10 in descending order. The LIFO operation basically gives that the 10th card which was presumably added last becomes the first to be popped off in a case of data removal. However…… This is not the same for queues.

Queues use the FIFO (first in, first out) for push and pop operations.

Back to the deck of cards analogy, in the case of a queue, the first card would be the first to leave the deck in this instance.

IMPLEMENTING STACKS AND QUEUES IN PYTHON

Stacks and Queues are implemented in the deque object of the collections module.

We import the deque class off of the collections module and instantiate it.

from collections import deque
dataStructure = deque([‘a’, ’b', ’c', ’d', ’e'])

CHAINLINK: IMPLEMENTING LINKED LISTS IN PYTHON

In my Linked lists article, I inserted a pic where I listed all possible operations implemented in the deque class. Here, we will be going over appending into and popping data off the deque.

Adding elements to the deque

dataStructure.append('f')
>>> deque([‘a’, ’b', ’c', ’d', ’e', 'f'])

This pushes an element into the deque.

REMOVING ELEMENTS FROM THE QUEUE

Here, we’d have to respect LIFO and FIFO depending on the data structure (stacks or queues) we are implementing. For stacks, we remove elements from the last index, and for the queue, we remove them from the first index. The deque happens to have methods to suit our needs. For stacks, we use the pop method, for queues, we use the popleft method.

#STACKS LIFO
deque.pop()
>>>  deque([‘a’, ’b', ’c', ’d', ’e'])
#QUEUES FIFO
deque.popleft()
>>> deque([’b', ’c', ’d', ’e', 'f'])

You could check out the linked list article for more deque operations.

CREATING CUSTOM STACKS AND QUEUES

Proficiency in object-oriented programming concepts is a plus when it’s about creating custom data structures.

STACKS

class Stack:
    def __init__(self):
        self.structure = []
    def push(self, element):
        self.structure.append(element)
    def pop(self):
        if len(self.structure) < 1:
            return None
        return self.structure.pop()

Here, we create a Stacks class and a constructor which holds structure , a list which is the data structure I choose to use, however, you could use an array or any other linear data structure that’s flexible enough to fit your needs. The push method appends to the self.structure list whatever is passed in. The pop method is written such that it checks if there’s an element first and then pops off the last element if any.

QUEUES

class Queue:
    def __init__(self):
        self.structure = []
    def push(self, element):
        self.structure.append(element)
    def popleft(self):
        if len(self.structure) < 1:
            return None
        return self.structure.pop(0)

The only differences in both data structures are the orientation used for removing elements, they share alike implementations. pop(0) is used in the queue to specify removal of the first element as the pop method removes from the back on default.

That’s it, now you understand how stacks and queues work, can be implemented and customized.