How to implement Stack in Python?

Introduction

Stacks is one of the most fundamental data structures used in computer science. A stack is a last-in, first-out (LIFO) data structure that allows elements to be added and removed from one end, known as the “top” of the stack. In this blog post, we’ll explore how to implement a Stack from scratch in Python. We’ll also discuss using Python’s in-built mechanisms to achieve stack-like behavior.

The Stack Data Structure

The operations commonly associated with a stack include:

1. Push: To add an element to the top of the stack.
2. Pop: To remove and return the top element from the stack.
3. Peek/Top: To look at the top element without removing it.
4. isEmpty: To check whether the stack is empty.
5. getSize: To get the number of elements in the stack.

Implementing a Stack from Scratch

We can implement a stack using either a list or a custom linked list. Here we’ll use Python’s built-in list structure. Python’s built-in list can easily be used as a stack.

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

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

    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()
        else:
            return "Stack is empty"

    def peek(self):
        if not self.isEmpty():
            return self.stack[-1]
        else:
            return "Stack is empty"

    def isEmpty(self):
        return len(self.stack) == 0

    def getSize(self):
        return len(self.stack)

# Example usage
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())  # Output will be 3
print(s.peek())  # Output will be 2
print(s.isEmpty())  # Output will be False
print(s.getSize())  # Output will be 2

Using Python’s In-Built Stack Mechanisms

Using Python List Directly

Python lists are dynamic arrays that provide fast O(1) append and pop operations. These can be used directly as a stack.

# Initialize stack
stack = []

# Push elements
stack.append(1)
stack.append(2)
stack.append(3)

# Pop elements
print(stack.pop())  # Output will be 3

# Peek into the stack
print(stack[-1])  # Output will be 2

Using collections.deque

Python’s collections.deque can also be used as a stack, with fast O(1) appends and pops from both ends.

from collections import deque

# Initialize stack
stack = deque()

# Push elements
stack.append(1)
stack.append(2)
stack.append(3)

# Pop elements
print(stack.pop())  # Output will be 3

# Peek into the stack
print(stack[-1])  # Output will be 2

Summary

We have seen how to implement a stack data structure from scratch in Python, using built-in lists. Additionally, we looked at Python’s in-built mechanisms like lists and collections.deque to achieve stack functionality.