Stacks And Queues

Stacks and queues are the most commonly used data structures in web development. Stacks use the LIFO accounting method, Last-In/First-Out. In contrast, a queue stores items in a FIFO method, First-In/First-Out. Your history in your web browser and the undo operation in applications were made possible using stacks. Handling sequential events in web browsers uses queues.

Implementing a Queue

We will leverage Pythons deque collection from the standard library instead of a python list. Both allow for enqueuing elements using their .append() methods, but a list can occasionally require copying all elements to a new memory location. Also, dequeuing is far less efficient than using deque.popleft() method.

from collections import deque

class Queue:
    def __init__(self):
        # the '_' leading elements indicate an internal/private bit
        self._elements = deque()

    def enqueue(self, element):
        self._elements.append(element)

    def dequeue(self):
        return self._elements.popleft()

NewQueue = Queue()
NewQueue.enqueue("One")
NewQueue.enqueue("Two")
NewQueue.enqueue("Three")

NewQueue.dequeue()
# One
NewQueue.dequeue()
# Two
NewQueue.dequeue()
# Three

Essentially, this is all we need to implement a primary queue. We can improve on this class by allowing initial elements and allowing to report queue length.

def __init__(self, *elements):
    self._elements = deque(elements)

def __len__(self):
    return len(self._elements)


NewQueue = Queue("One", "Two", "Three")
len(NewQueue)
# 3

Implementing a Stack

Implementing a stack is simple; we can extend our Queue class and override our dequeue method to remove it from the top of the stack.

class Stack(Queue):
    def dequeue(self):
        return self._elements.pop()
    
NewStack = Stack("First", "Second", "Third")
NewStack.dequeue()
# Third
NewStack.dequeue()
# Second
NewStack.dequeue()
# First

That’s it! We’re now able to define and implement a stack and queue.

Relevant links

Collections Deque