5 Best Ways to Implement a Stack in Python

5/5 - (2 votes)

πŸ’‘ Problem Formulation: A stack is a fundamental data structure that follows a Last In, First Out (LIFO) protocol. It’s a collection that allows for efficient data access with push and pop operations. In Python, there are several ways to implement a stack, each with its own benefits. This article explores different methods, with examples demonstrating a stack that takes integers as input and allows viewing of the last element pushed onto the stack as the output.

Method 1: Using Python List

The most straightforward method to implement a stack is using Python’s built-in list. Lists provide built-in methods such as append() for push and pop() for pop operations that can be used to manipulate stacks easily.

Here’s an example:

class ListStack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

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

    def peek(self):
        return self.items[-1] if not self.is_empty() else None

stack = ListStack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek())

Output: 3

The ListStack class encapsulates a list and provides stack-specific operations. The peek() method returns the last item without removing it. This code is simple and uses the dynamic array structure of Python list.

Method 2: Using Collections.deque

The deque from collections module is an alternative to list that is optimized for operations that pop or append items from either end of a sequence with constant O(1) performance.

Here’s an example:

from collections import deque

class DequeStack:
    def __init__(self):
        self.items = deque()

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

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

    def peek(self):
        return self.items[-1] if not self.is_empty() else None

stack = DequeStack()
stack.push('apple')
stack.push('banana')
stack.push('cherry')
print(stack.peek())

Output: cherry

The DequeStack class uses a deque for more efficient append and pop actions. This method is great for larger datasets where performance is crucial.

Method 3: Using LifoQueue from queue Module

The LifoQueue class from Python’s queue module provides synchronisation features which could be useful when implementing stacks for multi-threaded programming.

Here’s an example:

from queue import LifoQueue

stack = LifoQueue()

stack.put('apple')
stack.put('banana')
stack.put('cherry')

print(stack.get())

Output: cherry

The LifoQueue allows thread-safe operations on the stack. The get() method in LifoQueue performs the operation of pop. It is convenient but lacks a non-blocking peek operation.

Method 4: Using LinkedList

A linked list can be used to create a stack by enforcing LIFO operations where the last element added is the first to be removed. It involves more manual control but is excellent for understanding the inner workings of a stack.

Here’s an example:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedListStack:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.is_empty():
            return None
        pop_node = self.head
        self.head = self.head.next
        pop_node.next = None
        return pop_node.value

    def peek(self):
        return self.head.value if not self.is_empty() else None

stack = LinkedListStack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.peek())

Output: 30

Our LinkedListStack class demonstrates a stack with a singly linked list structure. Each node points to the next node, and the stack operations adjust the head of the list accordingly.

Bonus One-Liner Method 5: Stack as a Composition from List

For simplicity, one can also create a stack by only using a composition of Python’s list without creating a class, taking advantage of the fact that lists already implement stack methods.

Here’s an example:

stack = []
stack.append('apple')
stack.append('banana')
stack.append('cherry')

print(stack[-1]) #peek

Output: cherry

This one-liner makes use of Python’s list and its methods to perform stack operations. It’s elegant for writing concise code but does not encapsulate the stack’s behavior within a class.

Summary/Discussion

  • Method 1: Using Python List. Simple and straightforward with Python’s direct list manipulation. Weakness: Not as performance-efficient for large stacks.
  • Method 2: Using Collections.deque. Efficient for large data operations. Weakness: No significant weakness, although it is more complex than using a list.
  • Method 3: Using LifoQueue from queue Module. Thread-safe operations for multi-threading environments. Weakness: Lacks a non-blocking peek operation.
  • Method 4: Using LinkedList. Good for a deeper understanding of stack operations. Weakness: More complex and involves manual management of the data structure.
  • Bonus One-Liner Method 5: Stack as a Composition from List. Quick and easy for very simple implementations. Weakness: Does not properly encapsulate stack data structure and operations.