MinStack.hh

/******************************************************************************
 * File: MinStack.hh
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * A LIFO stack class that supports O(1) push, pop, and find-min.  Here, the
 * find-min operation returns (but does not remove) the minimum value in the
 * stack.  This sort of stack is often used as a subroutine in other problems.
 * It can be used to construct a queue with equivalent properties by
 * using one of the many stack-to-queue constructions, for example.
 *
 * The implementation of the min-stack is actually quite simple.  The idea is
 * that since the stack can only grow and shrink at the top, we only need to
 * consider two ways that the minimum element of the stack can change:
 *
 *  1. The minimum element is on the top, and it is popped off, and
 *  2. A new element is added to the stack that is smaller than the minimum.
 *
 * Because of this, we can augment a standard stack to track the minimum value
 * as follows.  Whenever we push an element atop the stack, we compare it to
 * the current minimum value.  If it is smaller, we augment the value we just
 * added into the stack by recording that it is the minimum.  If not, we store
 * a pointer down to the element of the stack that actually is the minimum.  In
 * this way, we can find the minimum element in constant time by simply
 * inspecting the top element of the stack and following its pointer to the
 * minimum element.
 */
#ifndef MinStack_Included
#define MinStack_Included

#include <deque>
#include <functional> // For std::less
#include <utility>    // For std::pair

/**
 * Class: MinStack<T, Comparator = std::less<T>>
 * Usage: MinStack<int> myMinStack;
 * ----------------------------------------------------------------------------
 * A class representing a LIFO stack supporting constant-time push, pop, and
 * find-min.  The comparator may be customized.
 */
template <typename T, 
          typename Comparator = std::less<T> > 
class MinStack {
public:
  /**
   * Constructor: MinStack(Comparator = Comparator());
   * Usage: MinStack<T> myStack;
   *        MinStack<T, C> myStack(myComparator);
   * --------------------------------------------------------------------------
   * Constructs a new MinStack that uses the specified comparator to make
   * comparisons.
   */
  explicit MinStack(Comparator = Comparator());

  /**
   * void push(const T& val);
   * Usage: myStack.push(137);
   * --------------------------------------------------------------------------
   * Pushes a new element atop the stack.
   */
  void push(const T& val);

  /**
   * void pop();
   * Usage: myStack.pop();
   * --------------------------------------------------------------------------
   * Pops the top element off the stack.  If the stack is empty, the behavior
   * is undefined.
   */
  void pop();

  /**
   * const T& top() const;
   * Usage: cout << myStack.top() << endl;
   * --------------------------------------------------------------------------
   * Returns an immutable view of the top element of the stack.  If the stack
   * is empty, the behavior is undefined.
   */
  const T& top() const;

  /**
   * const T& min() const;
   * Usage: cout << myStack.min() << endl;
   * --------------------------------------------------------------------------
   * Returns an immutable view of the minimum element of the stack.  If the
   * stack is empty, the behavior is undefined.  If multiple elements in the
   * stack are tied for the minimum element, returns a reference to the lowest
   * (eldest) of them.
   */
  const T& min() const;

  /**
   * bool   empty() const;
   * size_t size()  const;
   * Usage: while (!myStack.empty()) { ... }
   *        if (myStack.size() == 3) { ... }
   * --------------------------------------------------------------------------
   * Returns whether the stack is empty and its size, respectively.
   */
  bool   empty() const;
  size_t size() const;

private:
  /* The actual stack.  Each entry is a pair of an element and the index of the
   * minimum element at or below this point.
   */
  std::deque< std::pair<T, size_t> > mStack;

  /* The comparator used to determine what the smallest element is. */
  Comparator mComp;
};

/* * * * * Implementation Below This Point * * * * */

/* Constructor stores the comparator for future use. */
template <typename T, typename Comparator>
MinStack<T, Comparator>::MinStack(Comparator c) 
  : mStack(), mComp(c) {
  // Handled in initialization list
}

/* Size and empty queries forward directly to the underlying deque. */
template <typename T, typename Comparator>
size_t MinStack<T, Comparator>::size() const {
  return mStack.size();
}
template <typename T, typename Comparator>
bool MinStack<T, Comparator>::empty() const {
  return mStack.empty();
}

/* Returning the top element looks at the back of the deque. */
template <typename T, typename Comparator>
const T& MinStack<T, Comparator>::top() const {
  return mStack.back().first;
}

/* Returning the min element looks at the element in the deque that is the
 * smallest so far.  It's held at the index at the top of the stack. */
template <typename T, typename Comparator>
const T& MinStack<T, Comparator>::min() const {
  return mStack[mStack.back().second].first;
}

/* Inserting a new element adds it to the stack and updates the minimum element
 * if the new element is smaller.
 */
template <typename T, typename Comparator>
void MinStack<T, Comparator>::push(const T& elem) {
  /* If the stack is empty, add the new element and mark that it's the smallest
   * so far.
   */
  if (empty()) {
    mStack.push_back(std::make_pair(elem, 0));
  }
  else {
    /* Otherwise, find the index of the smallest element and insert the new
     * element annotated with that index.
     */
    size_t smallestIndex = mStack.back().second;

    /* If this new element is smaller, the smallest element will now be at the
     * back of the list.
     */
    if (mComp(elem, min()))
      smallestIndex = mStack.size();

    /* Add the element in. */
    mStack.push_back(std::make_pair(elem, smallestIndex));
  }
}

/* Popping an element off the stack just removes the top pair from the
 * deque.
 */
template <typename T, typename Comparator>
void MinStack<T, Comparator>::pop() {
  mStack.pop_back();
}

#endif