Stack

DSA · Beginner

Definition

A stack is a Last-In-First-Out (LIFO) structure supporting push, pop and peek at one end.

Stacks drive function calls, undo features, expression parsing and bracket matching.

Diagram

Flowchart

Example: Valid parentheses

def valid(s):
    pairs = {')':'(', ']':'[', '}':'{'}
    st = []
    for c in s:
        if c in pairs:
            if not st or st.pop() != pairs[c]:
                return False
        else:
            st.append(c)
    return not st
print(valid('([]{})'))

Output: True

Complexity

push/pop/peek O(1)

Key points

LIFO order
Used in DFS and recursion
Monotonic stack solves next-greater problems

Interview questions

Implement a queue using stacks?

Use two stacks: push to one, pop from the other after transferring when empty.

What is a monotonic stack?

A stack kept in increasing or decreasing order to find next greater/smaller elements in O(n).