/*
 * Copyright (C) 2014 Pedro Vicente Gómez Sánchez.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.pedrovgs.problem63;

/**
 * How would you design an integer stack which, in addition to push and pop, also has a function
 * min which returns the minimum element? Push, pop and min should all operate in 0(1) time.
 *
 * @author Pedro Vicente Gómez Sánchez.
 */
public class ConstantComplexityOrderStack {

}

@@ -645,16 +645,41 @@
 lem63;%0A%0A
+import java.util.Stack;%0A%0A
 /**%0A * H
@@ -956,10 +956,868 @@
 tack %7B%0A%0A
+  /**%0A   * Approach based on a inner data structure to store the stack of integers and in the same object%0A   * the current min value we had when the element was pushed. With this approach we get a time%0A   * complexity order equals to O(1) but a space complexity order equals to O(N) where N is the%0A   * number of elements in the stack.%0A   */%0A  public static class Stack1 extends Stack%3CMinValue%3E %7B%0A%0A    public void push(int item) %7B%0A      int newMin = Math.min(item, getMin());%0A      super.push(new MinValue(item, newMin));%0A    %7D%0A%0A    public int getMin() %7B%0A      if (isEmpty()) %7B%0A        return Integer.MAX_VALUE;%0A      %7D else %7B%0A        return peek().minValue;%0A      %7D%0A    %7D%0A  %7D%0A%0A  static class MinValue %7B%0A    final int value;%0A    final int minValue;%0A%0A    MinValue(int value, int minValue) %7B%0A      this.value = value;%0A      this.minValue = minValue;%0A    %7D%0A  %7D%0A
 %7D%0A

Add first implementation to problem 63