minStack.h

minStack.h

//google的一道面试题，可以考虑用vector替换deque
#ifndef MIN_STACK_H
#define MIN_STACK_H

#include <vector>       //for vector
#include <utility>     //for pair
#include <functional>  //for std::less<T>
#include <limits>

template<typename T, typename Comparator = std::less<T> >
class MinStack{
public:
	explicit MinStack(Comparator c=Comparator());
	void Push(const T& elem);
	void Pop();
	const T& Top() const;
	const T& Min() const;
	bool Empty() const;
	size_t Size() const;
private:
	std::vector< std::pair<T, size_t> > m_stack;
	Comparator m_cmp;
};

template<typename T, typename Comparator>
MinStack<T, Comparator>::MinStack(Comparator c) : m_cmp(c){}

template<typename T, typename Comparator>
bool MinStack<T, Comparator>::Empty() const
{
	return m_stack.empty();
}

template<typename T, typename Comparator>
size_t MinStack<T, Comparator>::Size() const
{
	return m_stack.size();
}

template<typename T, typename Comparator>
const T& MinStack<T, Comparator>::Top() const
{
	return m_stack.back().first;
}

//没有处理stack为空的情况
template<typename T, typename Comparator>
const T& MinStack<T, Comparator>::Min() const
{
	return m_stack[m_stack.back().second].first;
}

template<typename T, typename Comparator>
void MinStack<T, Comparator>::Push(const T &elem)
{
	if (m_stack.empty())
		m_stack.push_back(std::make_pair(elem, 0));
	else
	{
		size_t smallestIndex = m_stack.back().second;
		if (m_cmp(elem, Min()))
			smallestIndex = m_stack.size();
		m_stack.push_back(std::make_pair(elem, smallestIndex));
	}
}

template<typename T, typename Comparator>
void MinStack<T, Comparator>::Pop()
{
	m_stack.pop_back();
}
#endif