栈和队列面试题（一）

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

思想：创建两个栈，一个为正常栈S，一个为最小元素栈Minstack，按元素入栈顺序将第一个元素入S和Minstack栈，然后将元素依次入栈，入栈时，将每个元素与Minstack栈的栈顶元素进行比较，如果该元素小于Minstack栈栈顶元素，就把该元素也放进Minstck栈，出栈时，判断出栈元素是否与Minstack栈的栈顶元素相同，若相同，则将该元素从S和Minstack栈中都弹出。返回最小值操作时，直接返回Minstack栈中的栈顶元素就可以了。

如下图所示，当入栈顺序为9，2，3，5，1，8时：

当所有元素全部入栈后：

代码实现：

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

typedef struct _stack
{
	int* _pElem;
	size_t _size;
	size_t _top;

	_stack(const int n)
		:_size(n)
	{
		_top = 0;
		_pElem = new int[n];
	}

	~_stack()
	{
		if (_pElem)
		{
			delete[] _pElem;
		}
	}
}_stack;

template<class T>
class Stack
{
public:
	Stack(int n)
		:s(n)
		,minstack(n)
	{}

	void Pop()
	{
		if (s._top == 0)
		{
			return;
		}

		int value = s._pElem[--s._top];
		--s._size;
		//判断将要出栈的是不是最小元素，
		if (value == minstack._pElem[minstack._top - 1])
		{
			--minstack._top;
			--minstack._size;
		}
	}

	void Push(const T value)
	{
		if (s._top == s._size)
		{
			return;
		}

	//如果当前最小元素栈为空或者要压入的元素小于等于当前最小元素 则压入
	//这里不需要担心最小栈溢出 因为前面已经判断并且top==0必须放在||前面 否则top==0时访问top-1会越界
	//注意这里必须是<=而不能是= 比如1 2 3 1 当1弹出时，最小元素仍然是1 因此minstack里面应该有两个1  
		if (minstack._top == 0 || value <= minstack._pElem[minstack._top - 1])
		{
			minstack._pElem[minstack._top++] = value;

		}
		s._pElem[s._top++] = value;


	}

	T& Min()
	{
		assert(minstack._size >= 0);
		return minstack._pElm[minstack._top];
	}

private:
	_stack s;
	_stack minstack;
};

test.c

void Test()
{
	Stack<int> s(5);
	s.Push(9);
	s.Push(7);
	s.Push(10);
	s.Push(5);
	s.Push(8);

	s.Pop();
	s.Pop();
	s.Pop();
	s.Pop();
	s.Pop();
}

这样就实现了题目所要求的功能，这里只是粗略实现了题目要求，并没有实现栈的其他函数，有兴趣的同学可以把也实现一下！

栈的其他函数