#include <iostream>
using namespace std;
typedef struct MinStackElement {
int val;
MinStackElement* next;
MinStackElement():
val(0),
next(NULL){}
MinStackElement(int val_) :
val(val_),
next(NULL){}
} MinStackElement;
typedef struct MinStackElementInMin {
MinStackElement elem;
MinStackElementInMin* nextInMin;
MinStackElementInMin(int val_) {
elem.val = val_;
elem.next = NULL;
nextInMin = NULL;
}
} MinStackElementInMin;
class MinStack {
MinStackElement* stackHead;
MinStackElementInMin* stackMin;
public:
void push(int x) {
if (stackHead == NULL)
{
MinStackElementInMin* newElem = new MinStackElementInMin(x);
stackHead = (MinStackElement*) (newElem);
stackMin = newElem;
}
else
{
if (x <= stackMin->elem.val)
{
MinStackElementInMin* newElem = new MinStackElementInMin(x);
newElem->nextInMin = stackMin;
stackMin = newElem;
stackHead = (MinStackElement*) (newElem);
}
else
{
MinStackElement* newElem = new MinStackElement(x);
newElem->next = stackHead;
stackHead = newElem;
}
}
}
void pop() {
if (stackHead != NULL)
{
MinStackElement* deleted = stackHead;
if (deleted->val == stackMin->elem.val)
{
stackMin = stackMin->nextInMin;
stackHead = stackHead->next;
delete ((MinStackElementInMin*) (deleted));
}
else
{
stackHead = stackHead->next;
delete deleted;
}
}
}
int top() {
return stackHead->val;
}
int getMin() {
return stackMin->elem.val;
}
MinStack() :
stackHead(NULL),
stackMin(NULL) {}
};
int main() {
MinStack m;
m.push(-10);
m.push(14);
m.getMin();
m.getMin();
m.push(-20);
m.getMin();
cout << m.getMin();
m.top();
m.getMin();
m.pop();
m.push(10);
m.push(-7);
cout << m.getMin();
m.push(-7);
m.pop();
m.top();
cout << m.getMin();
m.pop();
// your code goes here
return 0;
}