CareerCup

struct stack{

int minvalue;
int array[MAX_SIZE];
int top;

}mystack;

whenever u push an element just update the value of minvalue.Rest all works like normal stack.

Push,Pop,find_minimum in O(1).

import java.util.*;

public class Stack {

	private ArrayList<Comparable> _list;
	private ArrayList<Comparable> _subListMin; 
	
	
	public Stack() {
		
		_list = new ArrayList<Comparable>();
		_subListMin = new ArrayList<Comparable>();
	}
	
	public void push(Comparable item) {
		
		_list.add(item);
		
		if(_subListMin.size()==0) {
			_subListMin.add(item);
			return;
		}
		
		Comparable lastMin =  _subListMin.get(_subListMin.size()-1);
		
		if(lastMin.compareTo(item) < 0) {
			_subListMin.add(lastMin);
		}
		else
		{
			_subListMin.add(item);
		}
	}
	
	public Comparable pop() {
	
		_subListMin.remove(_subListMin.size()-1);
		return _list.remove(_list.size()-1);
	}
	
	public Comparable findMinimum() {
		return _subListMin.get(_subListMin.size()-1);
	}
	
	private String listToString(ArrayList<Comparable> list)
	{
		String res = "";
		for(Comparable c:list) {
			res += c.toString() + ",";
		}
		if(res.length()>0) {
			res = res.substring(0,res.length()-1);
		}
		return res;
	}
	
	public void print() {
		
		System.out.println("Stack content = " + listToString(_list));
		System.out.println("Min = " + findMinimum());
	}
	
	public static void main(String[] args) {
		
		Stack s = new Stack();
	
		s.push(2);
		s.push(8);
		s.push(1);
		s.print();
		
		s.pop();
		s.print();
		
	}
	
}

Can you explain your code to store minimum value in subListMin?

Comparable lastMin =  _subListMin.get(_subListMin.size()-1);
		
		if(lastMin.compareTo(item) < 0) {
			_subListMin.add(lastMin);
		}
		else
		{
			_subListMin.add(item);
		}

It appears to me that it is not correct. How will subListMin change if I do,
push(1)
push(2)
push(3)
push(4)
push(5)
push(6)
push(7)
push(8)
push(10)
push(9)

Can you please give the Corresponding C or C++ code for this ?

hi