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

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

具体实现如下：

#include<iostream>
#include<stack>
#include<string>
#include<assert.h>
using namespace std;

template<class T>
class Stack
{
public:
	void Push(const T& x);
	void Pop();
	T& Min();
	void PrintS();
private:
	stack<T> Sk;//存放栈中所有元素的
	stack<T> MinSk;//存放栈中最小元素的
};
template<class T>
void Stack<T>::Push(const T& x)
{
	Sk.push(x);
	//当MinSk为空时，先存放一个元素；当比较入栈元素小于栈顶元素时，入栈
	if (MinSk.empty() || x < MinSk.top())
	{
		MinSk.push(x);
	}
}
template<class T>
void Stack<T>::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<class T>
T& Stack<T>::Min()
{
	assert(!MinSk.empty());
	return MinSk.top();
}
template<class T>
void Stack<T>::PrintS()
{
	if (Sk.empty())
	{
		cout << "stack is empty!" << endl;
		return;
	}
	stack<T> tmp = Sk;
	stack<T> 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<int> 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<string> s1;
	s1.Push("sssss");
	s1.Push("syikl");
	s1.Push("yyyyy");
	s1.Push("fffff");
	s1.Push("lllll");
	s1.PrintS();
	cout << s1.Min() << endl;
}

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

template<class T>
class Stack
{
public:
	Stack()
		:_arr(NULL)
		, _size(0)
		, _capacity(0)
	{}
	Stack(const Stack<T>& 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<T>& operator=(const Stack<T>& 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;
};