面试题_设计包含 min函数的栈

梦想游戏人
目录:
algorithm

设计包含 min函数的栈()

定义栈的数据结构,要求添加一个 minminmin函数,能够得到栈的最小元素。

要求函数 min、push以及 pop 的时间复杂度都是 O(1)。

  • #include <iostream>
  • using namespace std;
  • /*by hk 2015-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;
  • }
#include <iostream>
using namespace std;

/*by hk 2015-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;
}
Scroll Up