Stack

What is Stack?

Stack is a Last In First Out (LIFO) data structure, meaning that the last element added will be the first element to be removed.

Stack can be implemented using arrays or linked lists.

Key operations of a stack include:

Push: Add an element to the top of the stack.
Pop: Remove and return the top element of the stack.
Peek: Return the top element without removing it.

Operation	Big-O Time
Push	O(1)
Pop	O(1)
Peek / Top	O(1)

Real-World Applications of Stack

Undo/Redo functionality in text editors
Browser history
Recursion

Advantages and Disadvantages of Stack

Advantages:

Simple to implement and use, with O(1) time complexity for push and pop operations
Efficient for certain algorithms (e.g., depth-first search)
Useful for specific applications like recursion, expression evaluation, and backtracking

Disadvantages:

Limited access to elements (only the top element is accessible)
Fixed size if implemented using arrays (unless using dynamic arrays)
Not suitable for random access of elements
Can lead to underflow if popping from an empty stack

Stack Class Implementation

stack.py


class Stack:
    def __init__(self) -> None:
        self.items = []
 
    def __len__(self) -> int:
        return len(self.items)
 
    def __str__(self) -> str:
        return str(self.items)
 
    def is_empty(self) -> bool:
        return len(self.items) == 0
 
    def push(self, item: int) -> None:
        self.items.append(item)
 
    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("Stack Underflow: Cannot pop from an empty stack")
        return self.items.pop()
    
    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Stack Underflow: Cannot pop from an empty stack")
        return self.items[-1]
 
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
 
print(len(stack))
print(stack)
 
print(stack.pop())
print(stack.peek())
print(stack)

stack.py


class Stack:
    def __init__(self) -> None:
        self.items = []
        self.top = -1  # Index of the top element; -1 indicates an empty stack
 
    def __len__(self) -> int:
        return self.top + 1
 
    def __str__(self) -> str:
        return str(self.items[:self.top + 1])
 
    def is_empty(self) -> bool:
        return self.top == -1
 
    def push(self, item: int) -> None:
        self.top += 1
        self.items += [item]  # manually extend the list
 
    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("Stack Underflow: Cannot pop from an empty stack")
        item = self.items[self.top]
        self.top -= 1
        return item
    
    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Stack Underflow: Cannot pop from an empty stack")
        return self.items[self.top]
 
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
 
print(len(stack))
print(stack)
 
print(stack.pop())
print(stack.peek())
print(stack)

stack.py


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
 
class Stack:
    def __init__(self):
        self.top = None
        self.size = 0
 
    def __len__(self) -> int:
        return self.size
 
    def __str__(self) -> str:
        result = []
        current = self.top
        while current:
            result.append(current.value)
            current = current.next
        return str(result)
 
    def is_empty(self) -> bool:
        return self.size == 0
 
    def push(self, item: int) -> None:
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self.size += 1
 
    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("Stack Underflow: Cannot pop from an empty stack")
        popped_value = self.top.value
        self.top = self.top.next
        self.size -= 1
        return popped_value
 
    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Stack Underflow: Cannot pop from an empty stack")
        return self.top.value
 
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
 
print(len(stack))
print(stack)
 
print(stack.pop())
print(stack.peek())
print(stack)

Stack Visualization

Top → 0x5008

0x5000

0x5004

0x5008

← TOP

Stack Size: 3 |

Peek

Push

Pop

Animation Controls

Animation Speed (ms)

Stack Operations

Push to Stack

Pop from Stack

Peek at Top