면접 문제min 함 수 를 포함 하 는 스 택 을 설계 합 니 다.

min 함 수 를 포함 하 는 스 택 설계 ()
스 택 의 데이터 구 조 를 정의 합 니 다. minmin 함 수 를 추가 하여 스 택 의 최소 요 소 를 얻 을 수 있 습 니 다.
요구 함수 min, push 및 pop 의 시간 복잡 도 는 모두 O (1) 입 니 다.

#include <iostream>
using namespace std;

/*by hk 2012-7-1*/

#define MAX ((~(unsigned int )0)-1)/2

class stack
{
public:
	int stack_data[100];/*    */
	int stack_min[100];/*             */
	int iter;
	int iter_min;
	stack()
	{
		iter=0;	
		iter_min=1;
		stack_min[1]=MAX;
	}	
	
	void pop()
	{
		if(iter>0)
		{
			--iter;	
			--iter_min;
		}
	}
	
	void push(int x)
	{
		if(iter<99)
		{
			stack_data[iter++]=x;
			if(x<stack_min[iter_min-1])
			{
				stack_min[iter_min++]=x;
				stack_min[iter_min]=MAX;
			}
			else
			{
					stack_min[iter_min]=stack_min[iter_min-1];
					++iter_min;
			}	
		}
	}
	int min()
	{
		return stack_min[iter_min-1];		
	}
};


int main(int argc, char *argv[])
{
	stack stk;
	stk.push(7);
	stk.push(3);
	stk.push(2);
	stk.push(8);
	stk.push(1);
	stk.pop();
	cout<<stk.min();
	return 0;
}