Overview

  • A stack is a linear data structure that follows the Last In, First Out (LIFO) principle.
  • Operations are performed at one end, called the top of the stack.

Common Stack Operations

  1. Push: Add an element to the top of the stack.
  2. Pop: Remove the top element from the stack.
  3. Peek/Top: Retrieve the top element without removing it.
  4. isEmpty: Check if the stack is empty.

Implementation

Stacks can be implemented using:

  • Arrays/Lists
  • Linked Lists
# Stack Implementation using Python List
class Stack:
    def __init__(self):
        self.stack = []

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

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return None

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

# Example Usage
s = Stack()
s.push(10)
s.push(20)
print(s.pop())  # Output: 20

Applications of Stacks

1. Function Call Stack

  • Stacks are used in managing function calls in recursion.

2. Expression Evaluation

  • Convert infix to postfix or prefix expressions.
  • Evaluate postfix expressions.

3. Balancing Parentheses

  • Check if parentheses, brackets, or braces are balanced.
# Example: Balanced Parentheses

def is_balanced(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

# Example Usage
print(is_balanced("(())"))  # Output: True

4. Undo Mechanism

  • Used in applications like text editors to reverse operations.

5. Backtracking

  • Solve problems like finding paths in a maze, parsing expressions, etc.

6. Stock Span Problem

  • Find the number of consecutive days a stock price was less than or equal to today.

7. Largest Rectangle in Histogram

  • Use stack to calculate the largest rectangular area in a histogram.
# Example: Largest Rectangle in Histogram

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    heights.append(0)

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

# Example Usage
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))  # Output: 10

Common Stack Problems

  1. Valid Parentheses
    • Check if parentheses are balanced.
  2. Min Stack
    • Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time.
# Example: Min Stack
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def get_min(self):
        return self.min_stack[-1]

# Example Usage
min_stack = MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
print(min_stack.get_min())  # Output: -3
min_stack.pop()
print(min_stack.top())      # Output: 0
print(min_stack.get_min())  # Output: -2
  1. Daily Temperatures
    • Given a list of daily temperatures, return a list where each element is the number of days until a warmer temperature.
# Example: Daily Temperatures

def daily_temperatures(T):
    result = [0] * len(T)
    stack = []

    for i, temp in enumerate(T):
        while stack and T[stack[-1]] < temp:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)

    return result

# Example Usage
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# Output: [1, 1, 4, 2, 1, 1, 0, 0]
  1. Next Greater Element
    • Find the next greater element for each element in an array.
# Example: Next Greater Element

def next_greater_element(nums):
    stack, result = [], [-1] * len(nums)

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            result[stack.pop()] = num
        stack.append(i)

    return result

# Example Usage
print(next_greater_element([2, 1, 2, 4, 3]))
# Output: [4, 2, 4, -1, -1]