CareerCup

using System.Collections.Generic;

public class FastMinStack<T>
{
    private readonly Stack<T> stack = new Stack<T>();
    // Could pass this in to the constructor
    private readonly IComparer<T> comparer = Comparer<T>.Default;

    private T currentMin;

    public T Minimum
    {
        get { return currentMin; }
    }

    public void Push(T element)
    {
        if (stack.Count == 0 ||
            comparer.Compare(element, currentMin) <= 0)
        {
            stack.Push(currentMin);
            stack.Push(element);
            currentMin = element;
        }
        else
        {
            stack.Push(element);
        }
    }

    public T Pop()
    {
        T ret = stack.Pop();
        if (comparer.Compare(ret, currentMin) == 0)
        {
            currentMin = stack.Pop();
        }
        return ret;
    }
}

Push into stack in sorted order.
As you can modify PUSH and POP.
implement both in sorted fashion.
the top of stack will have minimum element.
so every pop will give you the minimum element.

It can be done using two stacks. One for the element and other for the min.

Else you can modify the structure.

struct node
{
	int element;
	int min;
}

If even that can't be done. You can always push the minimum element behind the element.

class stack
{
	int* array;
	int size;
	int top;
	int min;
  
	stack(int s) { size = s; array = new int[2*s]; top = -1; min = INT_MAX; }
	~stack() { delete [] array };
	int pop();
	void push(int value);
	int get_min();
};

int stack::pop()
{
	if(top == -1)
		return INT_MIN;
	else
	{
		int t = array[top - 1];
		top = top - 2;
	}
}

int stack::get_min()
{
	if(top == -1)
		return INT_MIN;
	else
		return array[top];
}

void stack::push(int value)
{
	if(min > value)
		min = value;

	array[++top] = value;
	array[++top] = min;
}

While pushing elements, take a min pointer which always point to the minimum element. Every time you push, compare the coming element with the min element and change the min pointer accordingly. While retrieving the min element, push till you pop the min element.

This can be done using two stack. One, which is the actual stack and another stack which holds the minimum value seen till now at the top.

class MinStack {
	private Stack<Integer> theStack;
	private Stack<Integer> minStack;

	public MinStack() {
		this.theStack = new Stack<Integer>();
		this.minStack = new Stack<Integer>();
	}

	public void push(int value) {
		if(value <= this.min()) {
			this.minStack.push(value);
		}
		this.theStack.push(value);
	}

	public int pop() {
		int value = theStack.pop();
		if(value == this.min()) {
			value = this.minStack.pop();
		}
		return value;
	}

	public int min() {
		if(this.minStack.size() == 0) {
			return Integer.MAX_VALUE;
		}
		return this.minStack.peek();
	}
}

use another stack to keep track of minimum
stack 1 : stack 2:
push 2 push 2

stack 1: stack 2:
push 4 dont do anything

stack 1: stack 2:
push 1 push 1

Stacks contain the following:
stack 1: 1 4 2
stack 2: 1 2

When we pop from S1 check if it is equal to top of stack 2, if so pop from both stacks

void minStack(Struct Stack *s,int *min)
{
if(!isStackEmpty(s))
{
x=pop(s);
if(x<*min) *min = x;
minStack(s,min);
push(s,x);
}
}

use 2 stacks .
2nd stack to keep track of current minimum.
time complexity O(1)