Cracking The Coding Interview 3.2

//How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

//使用一个链表来记录最小值的index

#include <iostream>

using namespace std;

#define MAXSIZE 100

#define INIT -888888

class mStack

{

public:

	mStack()

	{

		top = -1;

		mi = new min;

		mi->data = 0;

		mi->nextMin = NULL;

		for (int i =0 ;i<100; i++)

		{

			data[i] = INIT;

		}

	}

	int pop()

	{

		if (top > -1)

		{

			if (top == mi->data)

			{

				min *t = mi;

				mi = mi->nextMin;

				delete t;

			}

			int c= data[top];

			data [top] = INIT;

			top --;

			return c;

		}

		else

			return -2;

	}

	bool push(int e)

	{

		if (top<MAXSIZE-1)

		{

			top++;

			data[top] = e;

			if (data[mi->data] > data[top] && data[top]!= INIT)

			{

				min *t = new min;

				t->data = top;

				t->nextMin = mi;

				mi = t;

			}

			return true;

		}

		else

		{

			return false;

		}

	}

	int getmin()

	{

		return data[mi->data];

	}

private:

	int data[MAXSIZE];

	int top;

	struct min

	{

		int data;

		min *nextMin;

	};

	min *mi;

};

int main()

{

	mStack s;

	for (int i=0;i<10;i++)

	{

		s.push(10-i);

	}

	s.pop();

	s.pop();

	cout<<s.getmin()<<endl;

	return 0;

}
巴特西

Cracking The Coding Interview 3.2

最新文章

热门文章
