实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)

实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)

创新互联建站坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站设计、网站建设、外贸网站建设、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的港口网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

具体实现如下：

#include
#include
#include
#include
using namespace std;

template
class Stack
{
public:
	void Push(const T& x);
	void Pop();
	T& Min();
	void PrintS();
private:
	stack Sk;//存放栈中所有元素的
	stack MinSk;//存放栈中最小元素的
};
template
void Stack::Push(const T& x)
{
	Sk.push(x);
	//当MinSk为空时，先存放一个元素；当比较入栈元素小于栈顶元素时，入栈
	if (MinSk.empty() || x < MinSk.top())
	{
		MinSk.push(x);
	}
}
template
void Stack::Pop()
{
	if (Sk.empty())
	{
		cout << "stack is empty!" << endl;
		return;
	}
	//如果出栈元素等于MinSk中栈顶元素，则MinSk需pop()该元素，使MinSk栈顶始终存放Sk栈中最小元素
	if (Sk.top() == MinSk.top())
	{
		MinSk.pop();
	}
	Sk.pop();
}
template
T& Stack::Min()
{
	assert(!MinSk.empty());
	return MinSk.top();
}
template
void Stack::PrintS()
{
	if (Sk.empty())
	{
		cout << "stack is empty!" << endl;
		return;
	}
	stack tmp = Sk;
	stack mintmp = MinSk;
	cout << "stack: ";
	while (!tmp.empty())
	{
		cout << tmp.top() << " ";
		tmp.pop();
	}
	cout << "\nminstack: ";
	while (!mintmp.empty())
	{
		cout << mintmp.top() << " ";
		mintmp.pop();
	}
	cout << endl;
}
//测试用例
void Test4()
{
	//Stack s1;
	//s1.Push(9);
	//s1.Push(5);
	//s1.Push(7);
	//s1.Push(3);
	//s1.Push(8);
	////s1.Pop();
	////s1.Pop();
	////s1.Pop();
	////s1.Pop();
	////s1.Pop();
	////s1.Pop();
	Stack s1;
	s1.Push("sssss");
	s1.Push("syikl");
	s1.Push("yyyyy");
	s1.Push("fffff");
	s1.Push("lllll");
	s1.PrintS();
	cout << s1.Min() << endl;
}

【干货小知识】自主实现一个栈，具体实现如下：

template
class Stack
{
public:
	Stack()
		:_arr(NULL)
		, _size(0)
		, _capacity(0)
	{}
	Stack(const Stack& s)
		:_arr(new T[s._size])
		, _size(s._size)
		, _capacity(s._size)
	{
		for (size_t i = 0; i < _size; i++)
		{
			_arr[i] = s._arr[i];
		}
	}
	Stack& operator=(const Stack& s)
	{
		if (this != &s)
		{
			T* tmp = new T[s._size];
			delete[] _arr;
			for (size_t i = 0; i < s._size; i++)
			{
				tmp[i] = s._arr[i];
			}
			_arr = tmp;
			_size = s._size;
			_capacity = s._capacity;
		}
		return *this;
	}
	~Stack()
	{
		if (_arr)
		{
			delete[] _arr;
		}
	}
public:
	void _CheckCapacity(size_t size)
	{
		if (size > _capacity)
		{
			_capacity += _capacity * 2 + 3;
		}
		T* tmp = new T[_capacity];
		if (_arr)
		{
			for (size_t i = 0; i < _size; i++)
			{
				tmp[i] = _arr[i];
			}
		}
		delete[] _arr;
		_arr = tmp;
	}
	void Push(const T& x)
	{
		_CheckCapacity(_size + 1);
		_arr[_size++] = x;
	}
	void Pop()
	{
		assert(_size > 0);
		--_size;
	}
	bool Empty()
	{
		return _size == 0;
	}
	size_t Size()
	{
		return _size;
	}
	T& Top()
	{
		return _arr[_size - 1];
	}
	void PrintStack()
	{
		if (_size == 0)
		{
			cout << "Stack is empty!";
		}
		else
		{
			for (size_t i = 0; i < _size; i++)
			{
				cout << _arr[i] << " ";
			}
			cout << endl;
		}
	}
private:
	T* _arr;
	size_t _size;
	size_t _capacity;
};

分享名称：实现一个栈，要求实现Push（入栈）、Pop（出栈）、Min（返回最小值的操作）的时间复杂度为O(1)
链接地址：http://cdiso.cn/article/jeeecj.html