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: Define a variable min that stores the current minimum element in the stack. Now the interesting part is, how to handle the case when minimum element is removed. To handle this, push "2x – min" into the stack instead of x so that previous minimum element can be retrieved using current min and its value stored in stack. Below are detailed steps and explanation of working.
Push(x) : Inserts x at the top of stack.

• If stack is empty, insert x into the stack and make min equal to x.
• If stack is not empty, compare x with min. Two cases arise:
  • If x is greater than or equal to min, simply insert x.
  • If x is less than minEle, insert (2*x – min) into the stack and make min equal to x. 

Pop() : Removes an element from top of stack.

• Remove element from top. Let the removed element be y. Two cases arise:
  • If y is greater than or equal to minEle, the minimum element in the stack is still min.
  • If y is less than min, the minimum element now becomes (2*min – y), so update (min = 2*min – y). This is where we retrieve previous minimum from current minimum and its value in stack. 

Important Points:

• Stack doesn’t hold actual value of an element if it is minimum so far.
• Actual minimum element is always stored in min.
  
  
  

typedef struct  {
	stack original;
	int min;
} Specialstack;

Specialstack CreateSpecialStack()
{
	Specialstack s;
	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);
		s->min=e;
	}
	else
	{
		if(e<s->min)
		{
			Push(&(s->original),2*e-s->min);
			s->min=e;
		}
		else
			Push(&(s->original),e);
	}
	return 1;
}

int PopSpecialStack(Specialstack *p)
{
	element el;
	if (isEmptyStack(p->original)) return 0;
	Top(p->original,&el);
	Pop(&(p->original));
	if(el < p->min)
	{
		p->min=2*p->min-el;
	}
	return 1;
}

int TopSpecialStack(Specialstack p, element *e)
{
	element el;
	if (isEmptyStack(p.original)) return 0;
	Top(p.original,&el);
	// If e < min means min stores value of t.
	*e=(el<p.min?p.min:el);
	return 1;
}

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