带有 min 方法的 stack 容器

要求：容器既能满足栈的基本操作，又能获得最小值。
思路：使用两个栈容器来实现。一个栈用于正常栈操作，另外一个栈容器用于获得最小值。实现时，最主要的是元素的入栈操作。具体步骤参考如下代码注释。

#include <iostream>
#include <stack>
using namespace std;

template<class T>
class MyStack
{
public:
	void pop()
	{
		m_stack.pop();
		m_min_stack.pop();
	}

	void push(const T &val)
	{
		m_stack.push(val);
		// 如果 m_min_stack 为空，则 val 即为当前最小元素
		// 如果 m_min_stack 不为空，则需要比较 val 与栈顶元素谁更小
		// 如果 val 更小，则将其压栈
		if (m_min_stack.empty() || val < m_min_stack.top())
		{
			m_min_stack.push(val);
			return;
		}

		// 如果栈顶元素更小，则将栈顶元素重复压栈
		m_min_stack.push(m_min_stack.top());
	}

	T top()
	{
		return m_stack.top();
	}

	T min()
	{
		return m_min_stack.top();
	}

	size_t size()
	{
		return m_stack.size();
	}

	bool empty()
	{
		return m_stack.empty();
	}

private:
	stack<T> m_stack;
	stack<T> m_min_stack;
};


void test()
{
	MyStack<int> stack;
	stack.push(5);
	stack.push(8);
	stack.push(2);
	stack.push(1);
	stack.push(4);

	while (!stack.empty())
	{
		cout << stack.top() << " " << stack.min() << endl;
		stack.pop();
	}
}


int main()
{
	test();
	return 0;
}

程序输出结果：