DSA — Stacks

What is a Stack?

A Last-In-First-Out (LIFO) data structure.

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
    
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

Operations

Operation	Time Complexity
push	O(1)
pop	O(1)
peek	O(1)
is_empty	O(1)

Usage Examples

# Balanced parentheses
def is_balanced(expression):
    stack = Stack()
    for char in expression:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty():
                return False
            top = stack.pop()
            if (char == ')' and top != '(') or \
               (char == '}' and top != '{') or \
               (char == ']' and top != '['):
                return False
    return stack.is_empty()

Mini Practice

1. Implement a stack
2. Check balanced parentheses
3. Implement undo functionality
4. Convert infix to postfix

Up Next

Continue with Queues — queue data structure.