Programmer's Blog

Programmer's reference

[Java] monotonic stack class

import java.util.LinkedList;

public class MonotonicStack<T extends Comparable<T>> {
  private final LinkedList<T> stack = new LinkedList<>();

  public void push(T element) {
    while (!stack.isEmpty() && stack.peekLast().compareTo(element) > 0) {
      stack.removeLast();
    }
    stack.addLast(element);
  }

  public T pop() {
    return stack.removeLast();
  }

  public T peek() {
    return stack.peekLast();
  }

  public int size() {
    return stack.size();
  }

  public boolean isEmpty() {
    return stack.isEmpty();
  }
}

Leave a comment