Design A stack to get minimum in o(1) time.

Question: Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc.

Example:

Consider the following SpecialStack
16 –> TOP
15
29
19
18

When getMin() is called it should return 15, which is the minimum
element in the current stack.

If we do pop two times on stack, the stack becomes
29 –> TOP
19
18

When getMin() is called, it should return 18 which is the minimum
in the current stack.

Solution :=

Stack (Code) :

<br />#include<iostream>
#include<conio.h>
using namespace std;
struct stack
{
int data;
struct stack *link;
}*head=NULL,*nptr,*tmp,*ptr;

void push()
{
int d;
cout<<"Enter a data:\n";
cin>>d;
nptr=new stack;
if(nptr==NULL)
{
cout<<"Out of Memory...! Overflow...!!\n";
}
else
{
nptr->data=d;
nptr->link=head;
head=nptr;
cout<<"node has been inserted at top successfully !!\n";
}
}

void pop()
{
int info;
if(head==NULL)
{
cout<<"Underflow...!!\n";
}
else
{
tmp=head;
info=tmp->data;
head=head->link;
tmp->link=NULL;
delete tmp;
cout<<info<<" deleted from top..!!\n";
}
}

void display()
{
if(head==NULL)
{
cout<<"Stack is empty....!!!\n";
}
else
{
ptr=head;
cout<<"Head->";
while(ptr!=NULL)
{
cout<<"["<<ptr->data<<"] ->";
ptr=ptr->link;
}
cout<<"NULL";
}
}
int main()
{
int opn,elem;
do
{
cout<<"\n### Linked List Implementation of STACK Operations ###\n\n";
cout<<"\n Press 1-Push, 2-Pop, 3-Display,4-Exit\n";
cout<<"Your option ? ";
cin>>opn;
switch(opn)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3: cout<<"Linked List Implementation of Stack: Status:\n";
display(); break;
case 4: cout<<"\n Terminating \n\n"; break;
default: cout<<"\nInvalid Option !!! Try Again !! \n\n";
break;
}
cout<<"\n\n Press a Key to Continue . . . \n";
getch();
}while(opn != 4);

getch();
return 0;
}

corollary :