栈的定义--Stack

栈只允许在末端进行插入和删除的线性表。栈具有后进先出的特性（LIFO，Last In First Out）。

spacer.gif

问题：

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

问题分析：

根据栈的特性要实现入栈和出栈是比较容易的，只需要借助系统给的stack即可。但是最难的是要满足Min（返回最小值的操作）

的时间复杂度为O(1)

我们先来讨论最一般的思路：

思路1

使用一个变量来保存最小的值_min，每次入栈时让入栈的元素d和_min进行比较，如果d<_min则更新_min,否则不更新。

但是这存在一个很大的问题，如果最小值出栈了怎么办？

比如说有一个栈为：8,10,6,2,9.

则_min的值为2，9出栈的话那么_min的值不受影响。但是如果2出栈的话，则_min的值就无法得到。

思路2

既然只用一个变量没法解决这个问题，那我们就增加变量。_min 保存当前的最小值，_second 保存次小值。

但是在实现Pop的时候又出现了新的问题，如果_min和_second都出栈之后，_min和_second该如何更新？

假设有栈为8,10,6,2,9

_min为2，_second为6.当2出栈之后_min更新为_second,但是_second该如何更新？

思路3

既然需要不断的更新最小值，那就把所有的最小值给保存起来。

解决方案一：

每次push()和pop()时将数据和最小值同时压入。

spacer.gif

假设有一个栈 8 7 10 6 2 2 9

则存储的结构为：

spacer.gif

入栈时的操作：

1）如果栈为空或者入栈的元素d比当前栈的最小元素_s.top()._min小，则_min=d;

2）如果入栈元素d比当前栈的元素大于或者等于则直接将当前栈的最小值_s.top()._min赋给_min。

出栈操作：直接出栈

返回Min则 ：当栈不为空时，返回当前栈顶元素的_min即_s.top()._min。

实现代码：

//节点结构template
     
      struct Node{public:	T _data;//数据域	T _min;//当前最小值};//栈的实现template
      
       class Stack{public:	void Push(const T& d)	{		Node
       
         Data;		Data._data = d;//不能将d直接入栈，因为栈为一个结构体栈		if (_s.empty() || d < _s.top()._min)//如果栈为空或者入栈元素小于当前栈的最小值		{			Data._min = d;		}		else//入栈元素大于等于当前栈的最小值		{			Data._min = _s.top()._min;		}		_s.push(Data);//入栈	}	void Pop()	{		_s.pop();	}	T& Min()	{		if (_s.empty())		{			throw exception("栈为空");		}		return _s.top()._min;	}private:	stack
        
         
          > _s;};

总结：代码实现起来比较容易简洁，好理解可读性比较强，但是对于重复比较多的栈的元素的存取则比较浪费空间，

因为每次入栈和出栈时，都相当于入栈两次。

例如：8、6、6、6、9、5、5、5、5、10、2、2、11、2、2

解决方案二：

使用两个栈来实现。s1实现栈的push和pop，s2栈用于存储在push和pop过程中的最小值

比如有一组数要入栈： 8,10,6,2,9

S1： 8,10,6,2,9

S2： 8 6 2

每次入栈时，都会和S2.top 比较，如果小于S2.top 则会同时入S1和S2栈。

即到栈顶9时，最小值是2， 如果S1栈9出，和S2.top比较，如果大于S2.top，则S2不做任何操作，如果等于S2.top， 则S2.pop（）；

比如S1的2出栈时，2 == S2.top(), 然后S2.pop();这样就节省了很多空间。

但是上述方法还有问题：

比如数据

S1：8 7 10 6 2 2 2 9 这时

S2：8  7 6 2

当S1中2出栈时，S2中的2也会出栈，这样从S2中读取到的最小值就是6，但是明显错了。

解决方案：

既然栈中可能存在多个重复的最小值_min，解决方法有两种：

方法一：S2中每个元素添加一个计数器。这样当连续3次2出栈，S2中的2才出栈。

方法二：S2中入栈的时候将<=S2.top的元素统统入栈，即S2为8,7,6,2,2,2.

实现代码（计数器）：

template
     
      struct DataCount{public:	DataCount(const T & d)		:_data(d)		,_count(1)	{}public:	T _data;	int _count;};template
      
       class Stack{	//拷贝构造、赋值、均使用默认的即可，因为拷贝构造和赋值的时候调用的是stack的，不存在浅拷贝public:	void Push(const T &d)	{		_s.push(d);//d入数据栈		DataCount
       
         tmp(d);//由于_min为DataCount的栈，所以d不能直接入栈		if (_min.empty()|| d < _min.top()._data)//如果存放最小的栈为空或者小于		{			_min.push(tmp);		}		else if (d == _min.top()._data)//入栈的元素等于_min栈的栈顶元素，计数器_count+1;		{			_min.top()._count++;		}	}	void Pop()	{		if (_s.empty())		{			return;			//throw exception("栈为空");		}		//如果数据栈出栈的元素等于_min栈的栈顶元素		if (_s.top() == _min.top()._data)		{			if (_min.top()._count==1)//数据栈中最小的元素只有一个			{				_min.pop();			}			else//数据栈中存在多个相等的最小元素			{				_min.top()._count--;			}		}		//如果数据栈出栈的元素大于_min栈的栈顶元素		//由于_min栈中存放的都是较小的元素，所以不可能比数据栈要出栈的元素更大		_s.pop();	}	T& Min()	{		if (_min.empty())		{			//return -1;			throw exception("栈为空");		}		return _min.top()._data;	}private:	stack
        
          _s; //存储基本数据的栈	stack
         
          
           > _min; //存储最小值的栈};

实现代码（重复元素进栈）

template
     
      class Stack{public:	void Push(const T &d)	{		_s.push(d);//d入数据栈		if (_min.empty()|| d <= _min.top())//如果存放最小的栈为空或者入栈的元素小于等于_min栈的栈顶元素		{			_min.push(d);		}	}	void Pop()	{		if (_s.empty())		{			return;			//throw exception("栈为空");		}		//如果数据栈出栈的元素等于_min栈的栈顶元素		if (_s.top() == _min.top())		{			_min.pop();		}		//如果数据栈出栈的元素大于_min栈的栈顶元素		//由于_min栈中存放的都是较小的元素，所以不可能比数据栈要出栈的元素更大		_s.pop();	}	T& Min()	{		if (_min.empty())		{			//return -1;			throw exception("栈为空");		}		return _min.top();	}private:	stack
      
        _s; //存储基本数据的栈	stack
       
         _min; //存储最小值的栈};

比较：

方法一：

优点：适用于大量的重复的较小值的存储

缺点：在一般场景下空间浪费比较大，因为S2中每个元素添加一个计数器。

例如：8、6、6、6、9、5、5、5、5、10、2、2、11、2、2

使用计数器比较节省空间。

方法二：

优点：在一般场下比较节省空间。

缺点：对于大量的重复的较小值得存储比较浪费

例如：8、6、5、12、9、2、11、7

测试代码：  

void test(){	Stack
     
       s1;	s1.Push(10);	s1.Push(11);	s1.Push(6);	s1.Push(2);	s1.Push(2);	s1.Push(2);	s1.Push(12);	Stack
      
        s3(s1);	Stack
       
         s2;	s2 = s1;	try	{		cout << s1.Min() << endl;		s1.Pop();		cout << s1.Min() << endl;		s1.Pop();		cout << s1.Min() << endl;		s1.Pop();		cout << s1.Min() << endl;		s1.Pop();		cout << s1.Min() << endl;		s1.Pop();		cout << s1.Min() << endl;		s1.Pop();		cout << s1.Min() << endl;		s1.Pop();		cout << s1.Min() << endl;		s1.Pop();		cout << s1.Min() << endl;		s1.Pop();		cout << s1.Min() << endl;	}	catch (...)	{		cout << "栈为空" << endl;	}	try	{		cout << s2.Min() << endl;		s2.Pop();		cout << s2.Min() << endl;		s2.Pop();		cout << s2.Min() << endl;		s2.Pop();		cout << s2.Min() << endl;		s2.Pop();		cout << s2.Min() << endl;		s2.Pop();		cout << s2.Min() << endl;		s2.Pop();		cout << s2.Min() << endl;		s2.Pop();		cout << s2.Min() << endl;	}	catch (...)	{		cout << "栈为空" << endl;	}}int main(){	test();	getchar();	return 0;}