מריה בוטוסוב

יש לממש מחסנית מינימום ומקסימום (Min / Max Stack) פונקציה צריכה להחזיר תוצאה ב O(1)

//one implementation used dictionary
public class MinMaxStack {
	List<Dictionary<string, int>> minMaxStack = new List<Dictionary<string, int>>();
	List<int> stack = new List<int>();
		
	public int Peek() {
		return stack[stack.Count - 1];
	}
 
	public int Pop() {
		minMaxStack.RemoveAt(minMaxStack.Count - 1);
		var val = stack[stack.Count - 1];
		stack.RemoveAt(stack.Count - 1);
		return val;
	}
 
	public void Push(int number) {
		Dictionary<string, int> newMinMax = new Dictionary<string, int>();
		newMinMax.Add("min", number);
		newMinMax.Add("max", number);
		if(minMaxStack.Count > 0) {
			Dictionary<string, int> lastMinMax = new Dictionary<string, int> (minMaxStack[minMaxStack.Count - 1]);
			newMinMax["min"] = Math.Min(lastMinMax["min"], number);
			newMinMax["max"] = Math.Max(lastMinMax["max"], number);				
		}
		minMaxStack.Add(newMinMax);
		stack.Add(number);
	}
 
 
	public int GetMin() {
		return minMaxStack[minMaxStack.Count - 1]["min"];
	}
 
	public int GetMax() {
		return minMaxStack[minMaxStack.Count - 1]["max"];
	}
}
 
//other implementation - used 2 variables + additional values in stack
public class MinMaxStack {
	int max = Int32.MinValue;
	int min = Int32.MaxValue;
	Stack<int> stack = new Stack<int>();
	public int Peek() {			
		return stack.Peek();
	}
 
	public int Pop() {
		int value = stack.Pop();
		if(stack.Count <=2 ) {
			max = Int32.MinValue;
			min = Int32.MaxValue;
			stack = new Stack<int>();
		} else  {
		    if (value == min)
				 min = stack.Pop();
			if (value == max)
				max = stack.Pop();	
			}
			return value;
	}
 
	public void Push(int number) {
		if(number <= min) {
			stack.Push(min);
			min = number;
		}
		if(number >= max) {				
			stack.Push(max);
			max = number;
		}				
		stack.Push(number);
	}
 
	public int GetMin() {
		return min;
	}
 
	public int GetMax() {
		return max;
	}
}