Stack Data Structure

What is a Stack?

Stack is a linear data structure that operates based on Last In, First Out (LIFO) principle. This means that the last item added to the stack is the first one to be removed.

A stack supports the following primary operations:

push: Adds an element to the top of the stack.

pop: Removes the element from the top of the stack.

peek: Retrieves the element at the top of the stack without removing it.

is_empty: Checks whether the stack is empty or not.

size: Returns the number of elements in the stack.

Implementations of Stack With Python

We can implement stack array based or by linked list.

Get Seyedali Moradi (call me Sam)’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Here I develop both of them:

Using Arrays

class ArrayStack:
    """
    A stack implementation using an array(list) as underlying data structure.

    Attributes:
        _stack (list): The internal list used to store stack elements.

    Methods:
        push(element): Add an item to the top of the stack.
        pop(): Removes and returns the item from the top of the stack.
        peek(): Returns the item from the top of the stack.
        __len__(): Returns the size of the stack.
        is_empty(): Returns whether the stack is empty.
    """

    def __init__(self):
        self._stack = []

    def __len__(self):
        """Return the size of the stack."""

        return len(self._stack)

    def pop(self):
        """Remove and return the item from the top of the stack."""

        if len(self._stack) == 0:
            raise Exception("Stack is empty")
        else:
            return self._stack.pop()

    def push(self, item):
        """Add an item to the top of the stack."""

        self._stack.append(item)

    def peek(self):
        """Return the item from the top of the stack."""

        if len(self._stack) == 0:
            raise Exception("Stack is empty")
        else:
            return self._stack[-1]

    def is_empty(self):
        """Check if the stack is empty."""

        return len(self._stack) == 0

Using Linked Lists

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

class LinkedStack:
    """Stack implementation using linked list.

    Attributes:
        _head (Node): The last node in the stack.
        _size (int): The size of the stack.
    Methods:
        push(value): Add a node to as the new head of the stack.
        pop(): Removes and returns the head from the top of the stack.
        peek(): Returns the node data from the head of the stack.
        __len__(): Returns the size of the stack.
        is_empty(): Returns whether the stack is empty.
    """

    def __init__(self):
        self._head = None
        self._size = 0

    def __len__(self):
        """Returns the size of the stack."""

        return self._size

    def is_empty(self):
        """Returns whether the stack is empty."""

        return self._size == 0

    def push(self, value):
        """Adds a node as head to the top of the stack."""

        self._head = Node(value, self._head)
        self._size += 1

    def peek(self):
        """Returns the node data from the head of the stack."""

        if self._head is None:
            raise Exception('Stack is empty')
        return self._head.data

    def pop(self):
        """Removes head and returns its data from the top of the stack."""

        if self.is_empty():
            raise Exception('Stack is empty')
        head_data = self._head.data
        self._head = self._head.next
        self._size -= 1
        return head_data

Applications of Stacks

Some of stacks applications are:

1. Function Call Management.
2. Undo Operations.
3. Parsing.

Advantages and Disadvantages of Stacks

Advantages:

• Simple data structure to understand and easy to implement.
• Efficient for operations requiring LIFO principle.

Disadvantages:

• Limited access: Elements in a stack can only be accessed from the top.
• Not suitable for random access: Stacks do not allow for random access to elements.

Github repo:

https://github.com/sam1365/python-datastructure-and-algorithms/tree/main/stack