An Introduction to Data Structures in Python: Stacks and Queues

Stacks

Stacks are data structures based on lists and that follow the LIFO (Last In , First Out) storage method. In a stack, all operations affect the top item. In order to access the items lower in the stack, all the items above the desired item must be removed first.

To ‘Push’, or add, an item to the top of a stack, we simply use Python’s append() list-method. To ‘Pop’, or remove, the top item, we use the pop() method. We use the same method when we want to ‘Peek’, or just observe, what the top item is. ‘Clear’ removes all items from the stack.

A common use case of stacks in the real world is in undo commands. In a word processor, each of your most recent changes is Pushed to a stack. When we want to undo a change, we Pop it off.

In Python, we can either use a list or a wrapper class to represent a stack. As a wrapper class, we can make the commands more similar to those of a traditional stack:

class Stack():
    def __init__(self):
        self.stack = list()
    def push(self, item):
        self.stack.append(item)
    def pop(self):
        if len(self.stack) > 0:
            return self.stack.pop()
        else:
            return None
    def peek(self):
        if len(self.stack) > 0:
            return self.stack[len(self.stack) - 1]
        else:
            return None
    def __str___(self):
        return str(self.stack)

Queues

Queue’s are similar to stacks in that they can use lists and have similar functionality. The one difference is that queues are FIFO — First In, First Out. To add an item to the back of the queue, we ‘Enqueue’ that item. To remove one from the front, we ‘Dequeue’ it. Queues are used to model anything one would wait in line for, such as getting into a website with heavy traffic.

To enqueue an item, we use the append() method as we did with stacks. To remove an item, however, we use popleft(). This can feel unnatural because in English we’re used to reading left to right, but when using queues in python, we move right to left.

While we can use lists, a wrapper class can be used as well:

from collections import deque
class Queue():
    def __init__(self):
        self.queue = deque()
        self.size = 0
    def enqueue(self, item):
        self.queue.append(item)
        self.size += 1
        return self.queue
    def dequeue(self):
        if self.size > 0:
            self.size -= 1
            return self.queue.popleft()
        else:
            return None
    def get_size(self):
        return len(self.queue)