#include<iostream>
#include<stdlib.h>
using namespace std;
class Stack
{
private:
static const int max = 100;
int arr[max];
int top;
public:
Stack() { top = -1; }
bool isEmpty();
bool isFull();
int pop();
void push(int x);
};
bool Stack::isEmpty()
{
if(top == -1)
return true;
return false;
}
bool Stack::isFull()
{
if(top == max - 1)
return true;
return false;
}
int Stack::pop()
{
if(isEmpty())
{
cout<<"Stack Underflow";
abort();
}
int x = arr[top];
top--;
return x;
}
void Stack::push(int x)
{
if(isFull())
{
cout<<"Stack Overflow";
abort();
}
top++;
arr[top] = x;
}
//Stack
class SpecialStack: public Stack
{
Stack min;
public:
int pop();
void push(int x);
int getMin();
};
void SpecialStack::push(int x)
{
if(isEmpty()==true)
{
Stack::push(x);
min.push(x);
}
else
{
Stack::push(x);
int y = min.pop();
min.push(y);
if( x < y )
min.push(x);
else
min.push(y);
}
}
int SpecialStack::pop()
{
int x = Stack::pop();
min.pop();
return x;
}
int SpecialStack::getMin()
{
int x = min.pop();
min.push(x);
return x;
}
int main()
{
SpecialStack s;
s.push(10);
s.push(5);
s.push(20);
s.push(30);
cout<<s.getMin()<<endl;
s.push(1);
cout<<s.getMin();
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0ZGxpYi5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjbGFzcyBTdGFjawp7CnByaXZhdGU6CiAgICBzdGF0aWMgY29uc3QgaW50IG1heCA9IDEwMDsKICAgIGludCBhcnJbbWF4XTsKICAgIGludCB0b3A7CnB1YmxpYzoKICAgIFN0YWNrKCkgeyB0b3AgPSAtMTsgfQogICAgYm9vbCBpc0VtcHR5KCk7CiAgICBib29sIGlzRnVsbCgpOwogICAgaW50IHBvcCgpOwogICAgdm9pZCBwdXNoKGludCB4KTsKfTsKYm9vbCBTdGFjazo6aXNFbXB0eSgpCnsKICAgIGlmKHRvcCA9PSAtMSkKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIHJldHVybiBmYWxzZTsKfQpib29sIFN0YWNrOjppc0Z1bGwoKQp7CiAgICBpZih0b3AgPT0gbWF4IC0gMSkKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIHJldHVybiBmYWxzZTsKfQppbnQgU3RhY2s6OnBvcCgpCnsKICAgIGlmKGlzRW1wdHkoKSkKICAgIHsKICAgICAgICBjb3V0PDwiU3RhY2sgVW5kZXJmbG93IjsKICAgICAgICBhYm9ydCgpOwogICAgfQogICAgaW50IHggPSBhcnJbdG9wXTsKICAgIHRvcC0tOwogICAgcmV0dXJuIHg7Cn0Kdm9pZCBTdGFjazo6cHVzaChpbnQgeCkKewogICAgaWYoaXNGdWxsKCkpCiAgICB7CiAgICAgICAgY291dDw8IlN0YWNrIE92ZXJmbG93IjsKICAgICAgICBhYm9ydCgpOwogICAgfQogICAgdG9wKys7CiAgICBhcnJbdG9wXSA9IHg7Cn0KLy9TdGFjawoKY2xhc3MgU3BlY2lhbFN0YWNrOiBwdWJsaWMgU3RhY2sKewogICAgU3RhY2sgbWluOwpwdWJsaWM6CiAgICBpbnQgcG9wKCk7CiAgICB2b2lkIHB1c2goaW50IHgpOwogICAgaW50IGdldE1pbigpOwp9OwogCnZvaWQgU3BlY2lhbFN0YWNrOjpwdXNoKGludCB4KQp7CiAgICBpZihpc0VtcHR5KCk9PXRydWUpCiAgICB7CiAgICAgICAgU3RhY2s6OnB1c2goeCk7CiAgICAgICAgbWluLnB1c2goeCk7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgU3RhY2s6OnB1c2goeCk7CiAgICAgICAgaW50IHkgPSBtaW4ucG9wKCk7CiAgICAgICAgbWluLnB1c2goeSk7CiAgICAgICAgaWYoIHggPCB5ICkKICAgICAgICAgIG1pbi5wdXNoKHgpOwogICAgICAgIGVsc2UKICAgICAgICAgIG1pbi5wdXNoKHkpOwogICAgfQp9CmludCBTcGVjaWFsU3RhY2s6OnBvcCgpCnsKICAgIGludCB4ID0gU3RhY2s6OnBvcCgpOwogICAgbWluLnBvcCgpOwogICAgcmV0dXJuIHg7Cn0KaW50IFNwZWNpYWxTdGFjazo6Z2V0TWluKCkKewogICAgaW50IHggPSBtaW4ucG9wKCk7CiAgICBtaW4ucHVzaCh4KTsKICAgIHJldHVybiB4Owp9CmludCBtYWluKCkKewogICAgU3BlY2lhbFN0YWNrIHM7CiAgICBzLnB1c2goMTApOwogICAgcy5wdXNoKDUpOwogICAgcy5wdXNoKDIwKTsKICAgIHMucHVzaCgzMCk7CiAgICBjb3V0PDxzLmdldE1pbigpPDxlbmRsOwogICAgcy5wdXNoKDEpOwogICAgY291dDw8cy5nZXRNaW4oKTsKICAgIHJldHVybiAwOwp9Cg==