Suppose we add a new operation to the stack ADT called \(\texttt{findMinimum}\) that returns a reference to the smallest element in the stack. Show that it is possible to provide an implementation for \(\texttt{findMinimum}\) that has a worst case running time of O(1).
Hint: Keep two stack. One will be general stack, which will just keep the elements. The second will keep the min value.

• Push: Push an element to the top of stack1. Compare the new value with the value at the top of the stack2. If the new value is smaller, then push the new value into stack2. Alternatively, push the value at the top of the stack2 to itself once more.
• Pop: Pop an element from top of stack1 and return. Pop an element from top of stack2 too.
• Min: Read from the top of the stack2 this value will be the min.
  
  

typedef struct  {
	stack original, min;
} Specialstack;

Specialstack CreateSpecialStack()
{
	Specialstack s;
	s.min=s.original=CreateStack();
	return s;
}

int PushSpecialStack(Specialstack *s, element e)
{
	element el;
	if (isFullStack(s->original)) return 0;
	if(isEmptyStack(s->original))
	{
		Push(&(s->original),e);
		Push(&(s->min),e);
	}
	else
	{
		Push(&(s->original),e);
		Top(s->min,&el);
		if(e<el)
			Push(&(s->min),e);
		else
			Push(&(s->min),el);
	}
	return 1;
}

int PopSpecialStack(Specialstack *p)
{
	if (isEmptyStack(p->original)) return 0;
	Pop(&(p->original));
	Pop(&(p->min));
	return 1;
}

int TopSpecialStack(Specialstack p, element *e)
{
	stack s=p.original;
	if (isEmptyStack(p.original)) return 0;
	Top(s,e);
	return 1;
}

int getMin(Specialstack p, element *e)
{
	if (isEmptyStack(p.original)) return 0;
	Top(p.min,e);
	return 1;
}