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

創(chuàng)新互聯(lián)建站堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的港口網(wǎng)站設(shè)計(jì)、移動媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

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

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

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

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

新聞標(biāo)題：實(shí)現(xiàn)一個(gè)棧，要求實(shí)現(xiàn)Push（入棧）、Pop（出棧）、Min（返回最小值的操作）的時(shí)間復(fù)雜度為O(1)
標(biāo)題網(wǎng)址：http://weahome.cn/article/jeeecj.html