/******************************************************************************
* 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