包含min的栈

/***************************************************************
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素
的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)
***************************************************************/
#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;

template<typename T>
class minStack
{
public:
	void push(const T& data);
	void pop();
	const T& min();
	
private:
	stack<T> m_stackData;
	stack<T> m_stackMin;
};
template<typename T>
void minStack<T>::push(const T& data)
{
	m_stackData.push(data);
	if(m_stackMin.empty())
		m_stackMin.push(data);
	else
	{
		if(data<=m_stackMin.top())
			m_stackMin.push(data);
	}
}
template<typename T>
void minStack<T>::pop()
{
	assert(!m_stackData.empty() && !m_stackMin.empty());
	if(m_stackData.top() == m_stackMin.top())
		m_stackMin.pop();
	m_stackData.pop();
}

template<typename T>
const T& minStack<T>::min()
{
	assert(!m_stackData.empty() && !m_stackMin.empty());
	return m_stackMin.top();
}
void test()
{
	minStack<int> intMinStack;
	intMinStack.push(5);
	printf("%d\n",intMinStack.min());
	intMinStack.push(2);
	printf("%d\n",intMinStack.min());
	intMinStack.push(6);
	printf("%d\n",intMinStack.min());
	intMinStack.push(7);
	printf("%d\n",intMinStack.min());
	intMinStack.push(1);
	printf("%d\n",intMinStack.min());
	intMinStack.push(3);
	printf("%d\n",intMinStack.min());
	intMinStack.pop();
	printf("%d\n",intMinStack.min());
	intMinStack.pop();
	printf("%d\n",intMinStack.min());
	intMinStack.pop();
	printf("%d\n",intMinStack.min());
	intMinStack.pop();
	printf("%d\n",intMinStack.min());
	intMinStack.pop();
	printf("%d\n",intMinStack.min());
	intMinStack.pop();
}
int main()
{
	test();
	return 0;
}

包含min的栈,布布扣,bubuko.com

包含min的栈

原文：http://blog.csdn.net/walkerkalr/article/details/21079027