CareerCup

read Gayle's book for the right answer lol

First answer with each stack element containing and extra field min :

//
//  main.c
//  MinStack
//
//  Created by Srikant Aggarwal on 25/12/11.
//  Copyright 2011 NSIT. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

typedef struct stack_element
{
    int data;
    int min;
    struct stack_element *next;
} stack_element;

stack_element *top = NULL;

void push(int data)
{
    stack_element *temp = (stack_element *)malloc(sizeof(stack_element));
    temp -> data = data;
    temp -> next = top;
    
    if(top == NULL)
        temp -> min = data;
    else
    {
        if(data <= top -> min)
            temp -> min = data;
        else
            temp -> min = top -> min;
    }
    
    top = temp;
}

int pop()
{
    int data;
    
    if(top != NULL)
    {
        data = top -> data;
        stack_element *temp = top;
        top = top -> next;
        
        free(temp);
        temp = NULL;
        
        return data;
    }
    
    return -1;
}

int get_min()
{
    if(top != NULL)
        return top -> min;
    
    return -1;
}

int main (int argc, const char * argv[])
{
    int ans = 1;
    
    while(ans == 1)
    {
        int op, min;
        
        printf("\n1. Push\n2. Pop\n");
        scanf("%d", &op);
        
        if(op == 1)
        {
            int element;
            
            printf("\nPush Element = ");
            scanf("%d", &element);
            
            push(element);
            
            if((min = get_min()) != -1)
                printf("Min = %d\n", min);
        }
        else if(op == 2)
        {
            int element;
            
            if((element = pop()) != -1)
            {
                printf("\nPopping Element %d", element);
                
                if((min = get_min()) != -1)
                    printf("\nMin = %d\n", min);
                else
                    printf("\nStack Empty\n");
            }
            else
                printf("\nStack Empty\n");
        }
        else
            printf("\nInvalid operation\n");
        
        printf("\nContinue ? \n1. Yes\n2. No\n");
        scanf("%d", &ans);
    }
}

The best solution will be..
Create one more stake say min_stake contains the min value at the top.
While pushing just check the element which is pushed is less then min
if yes push this also to the min else do nothing.
while poping check if element is min.. pop the top most element also from
the min_stack.

this min_stack will contain the min element always at the top. provided all elements are diff.

If we are gonna get same elements we can store address of first occrance of min element in the min stack along with its value.

Do we need to keep the input order in the stack (2 stack answer) or we can change the order in stack to descend order (raghu's answer)

I think sb is right. All the solutions mentioned above suffer from calls to min element after some pops are done.

public class MinStack<T extends Comparable<T>> {
    private Stack<T> s1 = new LinkedList<T>();
    private Stack<T> s2 = new LinkedList<T>();

    public void push(T obj) {
        s1.push(obj);
        if (s2.empty()) {
            s2.push(obj);
        } else if (obj.compare(s2.top()) <= 0) {
            s2.push(obj);
        }
    }

    public void pop() {
        if (s1.empty()) {
            return;
        }
        T obj = s1.top();
        s1.pop();
        if (s2.empty()) {
            return;
        }
        if (obj.compare(s2.top()) == 0) {
            s2.pop();
        }
    }

    public T min() {
        if (s2.empty()) {
            return null;
        }
        return s2.top();
    }
}

I think the solution is:
1. Suppose push 5 in a empty stack.
2. Since it is first value, the min is 5. So push 5 and 5. The first one is data and the second one is min value. The min value is always at the top.
3. If 20 is pushed, pop 5 and compare it with 20. Because 20 is bigger, push 20 and 5.
4. If 2 is pushed, pop 5 and compare it with 2. Push 2 and 2 because now 2 is min.
5. If pop is asked, pop min, 2, and pop one more item. The second item will be returned and push 2. So the min value is always maintained at the top and stack will works as it suppose to.

1. Add a data member name e.g. minValue to Stack Data structure, and create a new StackB (it means you need at least 2 stack.
2. every time when you push a data into the stack.
a. if the stack is empty, the minValue = current push data
b. otherwise, compare the current data with minValue,
c. if current data > min Value, push the data to original stack and minValue to StackB
d. if current data < min value, minValue = current data, and push data to both stack and stackB
3. everytime when you pop a data, please pop 2 stacks together.
4. when you want to get the min value, please get top data of stackB

p.s: the data member minValue many not be necessary.

i think raghu is saying correct.we have to modify stack the stack so that it gives min value in constant time.every time when we push the value in stack we have to check it is less than min value then simply push into stack
if not less than then pop min value from stack,push other value in it and then push min value on the top of stack.
at every time we will have min value in top of the stack, so we can get min value in constant time....

correct if i am wrong.