//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;
}