Implement a Stack Data Structure in Python - Push, Pop, Peek

Updated: at 04:56 AM

A stack is a fundamental data structure used extensively in computer science and software engineering. It follows the last in, first out (LIFO) principle, where the last element added to the stack is the first one removed. Stacks have numerous applications, including managing function calls, implementing browsers’ back button, parsing, and more. Mastering stacks is an essential skill for any Python developer.

In this comprehensive guide, you will learn how to implement a stack data structure in Python using arrays, linked lists, or Python’s built-in list type. We will cover the key stack operations like push, pop, and peek with example code snippets. You will also learn various applications of stacks that demonstrate their utility. By the end, you will have a solid grasp of stacks in Python to ace technical coding interviews and solve real-world problems.

Table of Contents

Open Table of Contents

Overview of Stacks

A stack is an ordered collection of elements where additions and deletions are restricted to one end called the “top”. The opposite end of the stack is called the “base”. The basic operations are:

The push and pop operations follow a LIFO order. The peek operation retrieves the top element without modifying the stack.

Stack push pop operations

Stack Push and Pop Operations (Image Source: educative.io)

Some key properties of stacks:

Common uses of stacks:

Next, we will explore various ways to implement a stack data structure in Python focusing on the key push, pop, and peek operations.

Implementing a Stack in Python

There are several ways to implement a stack in Python:

  1. Using a Python list
  2. Using a Python deque
  3. Using a namedtuple
  4. Using a custom class

Let’s look at each of these implementations focusing on the push, pop, and peek operations.

Stack Implementation with Python List

The easiest way to implement a stack is using a Python list. Lists provide an ordered collection that can be modified easily. We can restrict inserts and deletes to one end of the list to emulate a stack.

Here is an example Stack class implemented using Python’s built-in list:

class Stack:
    def __init__(self):
        self.stack = []

    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[-1]
        else:
            return None

To use this stack:

stack = Stack()
stack.push(1)
stack.push(2)
print(stack.peek()) # Prints 2
print(stack.pop()) # Prints 2

The append() and pop() methods make insertion and deletion from the end of the list very efficient in O(1) constant time complexity. However, lists can expand dynamically so it utilizes more memory.

Stack Implementation with Python deque

Python’s deque class from the collections module provides a double ended queue that enables efficient appends and pops from both ends. This makes it a good alternative for stack implementation.

Here is an example using deque:

from collections import deque

class Stack:
    def __init__(self):
        self.container = deque()

    def push(self, val):
        self.container.append(val)

    def pop(self):
        return self.container.pop()

    def peek(self):
        return  self.container[-1]

To use:

stack = Stack()
stack.push(1)
print(stack.peek()) # 1

The deque allows efficient O(1) inserts and deletes from both ends. But it takes more memory than a list implementation.

Stack Implementation with namedtuple

Python’s namedtuple from the collections module can be used to add object orientation to a stack implementation.

Here is an example with namedtuple:

from collections import namedtuple

Stack = namedtuple('Stack', ['data', 'next'])

class Stack:
    def __init__(self):
        self.top = None

    def push(self, item):
        self.top = Stack(data=item, next=self.top)

    def pop(self):
        if self.top:
            data = self.top.data
            self.top = self.top.next
            return data
        else:
            return None

    def peek(self):
        if self.top:
            return self.top.data
        else:
            return None

To use:

stack = Stack()
stack.push(1)
print(stack.peek())

The namedtuple provides attributes to access the data and next pointer fields. But it utilizes more memory than the earlier implementations.

Stack Class Implementation

For full object orientation, we can implement a Stack class from scratch without using Python’s built-in types.

Here is an example custom Stack class implementation:

class StackNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, item):
        node = StackNode(item)
        node.next = self.top
        self.top = node

    def pop(self):
        if self.top is None:
            return None
        else:
            data = self.top.data
            self.top = self.top.next
            return data

    def peek(self):
        if self.top is None:
            return None
        else:
            return self.top.data

To use:

stack = Stack()
stack.push(1)
print(stack.peek())

This provides full class encapsulation and modularity at the cost of more memory usage.

So in summary, for stack implementation:

Pick the implementation that works best for your use case based on memory vs. performance tradeoffs.

Stack Applications and Examples

Now that we have explored various ways to implement a stack data structure in Python, let’s look at some common use cases and examples that demonstrate the power of stacks.

Balancing Symbols in Arithmetic Expressions

Stacks can be used to check if an arithmetic expression has balanced parenthesis, curly braces and square brackets.

When traversing the expression from left to right, we push each opening symbol onto the stack. When closing symbols are encountered, we compare them with the top of the stack to check if they match. If a matching opening symbol is found, it is popped off the stack.

At the end, if the stack is empty, the expression is balanced. Else it is unbalanced.

Here is an example implementation:

def balance_check(expression):
    stack = []
    opening = ['(', '{', '[']
    closing = [')', '}', ']']

    for char in expression:
        if char in opening:
            stack.append(char)
        elif char in closing:
            pos = closing.index(char)
            if ((len(stack) > 0) and
                (opening[pos] == stack[len(stack)-1])):
                stack.pop()
            else:
                return False

    if len(stack) == 0:
        return True
    else:
        return False

print(balance_check('[{()}]')) # True
print(balance_check('[{]}')) # False

This uses the stack to check for matching pairs efficiently in O(n) time complexity.

Evaluating Postfix Expressions

Stacks can evaluate postfix or reverse polish notation expressions where each operator follows its operands.

We scan the expression from left to right. Operands are pushed onto the stack. When an operator is encountered, the required number of operands are popped and the operator is applied. Finally, the output is the element remaining on the stack.

Here is a Python code snippet to evaluate postfix expressions:

def evaluate_postfix(expression):
    stack = []

    for char in expression:
        if char.isdigit():
            stack.append(int(char))
        else:
            rhs = stack.pop()
            lhs = stack.pop()
            if char == '+':
                stack.append(lhs + rhs)
            elif char == '-':
                stack.append(lhs - rhs)
            elif char == '*':
                stack.append(lhs * rhs)
            elif char == '/':
                stack.append(lhs / rhs)

    return stack.pop()

print(evaluate_postfix('35*62/+4-')) # 14

This uses the stack to efficiently compute prefix expressions.

Reversing a String

We can use a stack to reverse a given string.

The algorithm is:

This will reverse the order of characters.

Here is an example implementation:

def reverse_string(text):
    stack = []
    for char in text:
        stack.append(char)

    reversed_text = ''
    while stack:
        reversed_text += stack.pop()
    return reversed_text

print(reverse_string('algorithm')) # mhtirogla

This leverages the LIFO order of stacks to efficiently reverse text.

Implementing a Queue using Stacks

Queues follow FIFO order while stacks follow LIFO. But we can use two stacks to implement a queue.

The idea is to:

Here is a Python code example:

class QueueViaStacks:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, item):
        self.in_stack.append(item)

    def dequeue(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()

This leverages two stacks to achieve FIFO queue behavior.

Above were some examples of how stacks enable solving various computer science problems elegantly.

Summary

To summarize, here are the key points about implementing stacks in Python:

Stacks are fundamental data structures that have numerous applications. I hope this comprehensive guide provided you with a solid grounding on implementing stacks in Python along with common use cases. The key is mastering the push, pop and peek operations using any of the approaches described.

Happy coding with stacks!