Stacks in Java

Stacks are a fundamental data structure in Java and are widely used in Leetcode problems. They follow the Last-In-First-Out (LIFO) principle, meaning the last element added is the first one to be removed.

---

Table of Contents

1. Stack Basics
2. Common Stack Operations
3. Common Leetcode Patterns
4. Time and Space Complexity
5. Related Leetcode Questions

---

Stack Basics

• Definition: A stack is a linear data structure that follows the LIFO principle. Elements are added and removed from the top.

• Declaration:

  import java.util.Stack;
  
  Stack<Integer> stack = new Stack<>();

• Key Characteristics:

  • LIFO (Last-In-First-Out) order.
  • Commonly implemented using Stack class or Deque interface in Java.
  • Supports operations like push, pop, peek, etc.

---

Common Stack Operations

1. Adding an Element (Push)

• Method: push(E e)
• Example:

  stack.push(1);
  stack.push(2);

• Time Complexity: O(1)
• Space Complexity: O(1)

2. Removing an Element (Pop)

• Method: pop()
• Example:

  int element = stack.pop(); // Removes and returns the top element

• Time Complexity: O(1)
• Space Complexity: O(1)

3. Peeking at the Top Element

• Method: peek()
• Example:

  int topElement = stack.peek(); // Returns the top element without removing it

• Time Complexity: O(1)
• Space Complexity: O(1)

4. Checking if the Stack is Empty

• Method: isEmpty()
• Example:

  boolean isEmpty = stack.isEmpty(); // isEmpty = false

• Time Complexity: O(1)
• Space Complexity: O(1)

5. Size of the Stack

• Method: size()
• Example:

  int size = stack.size(); // size = 2

• Time Complexity: O(1)
• Space Complexity: O(1)

---

Common Leetcode Patterns

1. Parentheses Matching

• Used for problems like valid parentheses, minimum add to make parentheses valid, etc.
• Example:

  Stack<Character> stack = new Stack<>();
  for (char c : s.toCharArray()) {
      if (c == '(') {
          stack.push(c);
      } else if (c == ')') {
          if (stack.isEmpty() || stack.pop() != '(') {
              return false;
          }
      }
  }
  return stack.isEmpty();

• Related Questions:
  • Valid Parentheses
  • Minimum Add to Make Parentheses Valid
  • Longest Valid Parentheses

2. Next Greater Element

• Used for problems like next greater element, daily temperatures, etc.
• Example:

  Stack<Integer> stack = new Stack<>();
  int[] result = new int[nums.length];
  Arrays.fill(result, -1);
  for (int i = 0; i < nums.length; i++) {
      while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
          result[stack.pop()] = nums[i];
      }
      stack.push(i);
  }
  return result;

• Related Questions:
  • Next Greater Element I
  • Daily Temperatures
  • Next Greater Element II

3. Implementing Queues Using Stacks

• Used for problems like implementing a queue using stacks, stack using queues, etc.

• Example:

  import java.util.Stack;
  
  class MyQueue {
      Stack<Integer> input = new Stack<>();
      Stack<Integer> output = new Stack<>();
      public void push(int x) {
          input.push(x);
      }
      public int pop() {
          peek();
          return output.pop();
      }
      public int peek() {
          if (output.isEmpty()) {
              while (!input.isEmpty()) {
                  output.push(input.pop());
              }
          }
          return output.peek();
      }
      public boolean empty() {
          return input.isEmpty() && output.isEmpty();
      }
  }

• Related Questions:

  • Implement Queue using Stacks
  • Implement Stack using Queues

4. Monotonic Stack

• Used for problems like largest rectangle in histogram, trapping rain water, etc.
• Example:

  Stack<Integer> stack = new Stack<>();
  int maxArea = 0;
  for (int i = 0; i <= heights.length; i++) {
      int h = (i == heights.length) ? 0 : heights[i];
      while (!stack.isEmpty() && h < heights[stack.peek()]) {
          int height = heights[stack.pop()];
          int width = stack.isEmpty() ? i : i - stack.peek() - 1;
          maxArea = Math.max(maxArea, height * width);
      }
      stack.push(i);
  }
  return maxArea;

• Related Questions:
  • Largest Rectangle in Histogram
  • Trapping Rain Water
  • Remove K Digits

---

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Push (push())	O(1)	O(1)
Pop (pop())	O(1)	O(1)
Peek (peek())	O(1)	O(1)
Is Empty (isEmpty())	O(1)	O(1)
Size (size())	O(1)	O(1)

---

Related Leetcode Questions

Easy

1. Valid Parentheses
2. Implement Queue using Stacks
3. Min Stack

Medium

1. Next Greater Element I
2. Daily Temperatures
3. Largest Rectangle in Histogram

Hard

1. Trapping Rain Water
2. Remove K Digits
3. Longest Valid Parentheses