實(shí)現(xiàn)一個(gè)棧，要求實(shí)現(xiàn)Push（入棧）、Pop（出棧）、Min（返回最小值的操作）的時(shí)間復(fù)雜度為O(1)

實(shí)現(xiàn)一個(gè)棧，要求實(shí)現(xiàn)Push（入棧）、Pop（出棧）、Min（返回最小值的操作）的時(shí)間復(fù)雜度為O(1)

具體實(shí)現(xiàn)如下：

#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);
	//當(dāng)MinSk為空時(shí)，先存放一個(gè)元素；當(dāng)比較入棧元素小于棧頂元素時(shí)，入棧
	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;
}
//測(cè)試用例
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;
}

【干貨小知識(shí)】自主實(shí)現(xiàn)一個(gè)棧，具體實(shí)現(xiàn)如下：

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;
};