Stack

A Stack is a LIFO (Last In, First Out) data structure. The last element added is the first one removed. Think of a stack of plates: the top plate is the first one taken.

Basic Operations

• Push: Add an element on top of the stack.
• Pop: Remove an element from the top of the stack.
• Peek/Top: Look at the top element without removing it.
• isEmpty: Check whether the stack is empty.

# Stack using a Python list
stack = []

# Push
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)  # [10, 20, 30]

# Pop
top = stack.pop()
print(top)    # 30
print(stack)  # [10, 20]

# Peek
print(stack[-1])  # 20

# isEmpty
print(len(stack) == 0)  # False

Class Implementation

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

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

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[-1]

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

    def size(self):
        return len(self.items)

Time Complexity

Stack Applications

1. Undo/Redo: In text editors.
2. Bracket Matching: Validating balanced parentheses.
3. DFS: Graph traversal using a stack.
4. Call Stack: Managing recursive functions.
5. Backtracking: Solving mazes and puzzles.

Example: Balanced Parentheses

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
    return len(stack) == 0

print(is_balanced("({[]})"))  # True
print(is_balanced("([)]"))    # False

A Stack limits access to a single end. If you need access from both ends, use a Queue.