DSA Interview Prep · Lesson

Stack Implementation and Applications

Implement a stack with push/pop/peek, then solve valid-parentheses, min-stack, and evaluate reverse-polish notation.

The Stack Data Structure

A stack is a last-in, first-out (LIFO) data structure. The last element pushed is the first element popped. Think of a stack of plates: you can only add or remove from the top. Core operations are push (add to top), pop (remove from top), and peek (read top without removing). All three are O(1) on a well-implemented stack.

In Python, a list serves as a perfect stack: append is push, pop() is pop, and [-1] is peek.

stack = []

# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack)  # [10, 20, 30]

# Peek
print('Top:', stack[-1])       # 30

# Pop
print('Popped:', stack.pop())  # 30
print('After pop:', stack)     # [10, 20]

Stack Class with Push, Pop, Peek, isEmpty

Wrapping the list in a class provides a cleaner interface and prevents accidental use of non-stack operations like insert or indexing at positions other than the top. This is the implementation interviewers expect when asked to 'implement a stack from scratch'.

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

    def push(self, val):
        self._data.append(val)

    def pop(self):
        if self.is_empty():
            raise IndexError('pop from empty stack')
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError('peek at empty stack')
        return self._data[-1]

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

    def __len__(self):
        return len(self._data)

s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek())  # 3
print(s.pop())   # 3
print(len(s))    # 2

All lessons in this course

← Back to DSA Interview Prep