Skip to main content

Stacks

Premium

A stack is a linear data structure that stores items in a Last-In, First-Out (LIFO) order. The most recently inserted element is the first one removed. Stacks allow fast insertion and deletion at the top in O(1) time, but do not allow efficient random access.

They are commonly implemented using arrays or linked lists, and heavily used in algorithms involving recursion, undo/redo operations, expression evaluation, call stacks, parsing, DFS in graphs, and balanced parentheses.

Stack

Types of stacks

1. Simple stack

A simple stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle, the last element added is the first one removed. It supports basic operations like push(), pop(), and peek(), all in constant time. Stacks are used to manage function calls, validate expressions, and implement undo/redo features.

Common interview problems:

  • Valid Parentheses
  • Evaluate Reverse Polish Notation
  • Simplify Path
  • Implement Stack using Queues
Python
stack = []
stack.append(10)   # push
stack.append(20)
print(stack[-1])   # peek → 20
stack.pop()        # pop → removes 20

2. Monotonic increasing stack

A monotonic increasing stack maintains elements in non-decreasing order (each new element is greater than or equal to the one before it). While traversing an array, elements are popped from the stack when the current value is smaller, revealing useful relationships like previous smaller or next smaller elements.

Used for:

  • Finding the next smaller element
  • Solving Trapping Rain Water
  • Stock Span problem
  • Largest Rectangle in Histogram
Python
heights = [2, 1, 5, 6, 2, 3]
stack = []  # stores indices
for i, h in enumerate(heights):
    # Pop until stack is increasing
    while stack and heights[stack[-1]] > h:
        stack.pop()
    stack.append(i)

3. Monotonic decreasing stack

A monotonic decreasing stack keeps elements in non-increasing order (each new element is smaller than or equal to the previous one). When the current element is greater, items are popped — helping to find next greater or previous greater elements efficiently.

Used for:

  • Next Greater Element
  • Daily Temperatures
  • Maximum Rectangle in Histogram
Python
nums = [2, 1, 3, 5, 4]
stack = []  # stores indices
for i, num in enumerate(nums):
    # Pop while current is greater
    while stack and nums[stack[-1]] < num:
        stack.pop()
    stack.append(i)

Common stack operations

1. Push (add element to top)

stack = [] stack.append(10) # push 10 stack.append(20) # push 20

2. Pop (remove top element)

x = stack.pop() # removes and returns top

3. Peek / Top (view the top element)

top = stack[-1] # peek

Stack TC

Calculating memory usage

The memory footprint of a stack or queue depends on its underlying implementation — typically arrays are used to build fixed-size stacks and queues, whereas linked lists are used to build variable-sized stacks and queues.

Common edge cases & pitfalls

  1. Stack underflow: calling pop() when stack is empty

  2. Stack overflow: pushing too many items in a fixed-size stack

  3. Not checking empty before peek/pop

  4. Confusing stack with queue: stack is LIFO, queue is FIFO

  5. Recursive stack depth: deep recursion can exhaust call stack memory

Quiz

  1. What is the time complexity of push and pop in a stack?

a) O(n)

b) O(1)

c) O(log n)

d) O(n²)

  1. Which of the following uses a stack internally?

a) BFS

b) Hash tables

c) Depth-first search

d) Linked list merge

  1. Why are stacks useful for evaluating expressions?

a) They store elements in sorted order

b) They eliminate recursion

c) Operators and operands can be resolved in LIFO order

d) They guarantee O(1) traversal

Practice problems

Next Lesson