спроектировать стек таким образом, чтобы getMinimum () был равен O (1)

Вот моя версия реализации.

 struct MyStack {
    int element;
    int *CurrentMiniAddress;
 };

 void Push(int value)
 {
    // Create you structure and populate the value
    MyStack S = new MyStack();
    S->element = value;

    if(Stack.Empty())
    {    
        // Since the stack is empty, point CurrentMiniAddress to itself
        S->CurrentMiniAddress = S;

    }
    else
    {
         // Stack is not empty

         // Retrieve the top element. No Pop()
         MyStack *TopElement = Stack.Top();

         // Remember Always the TOP element points to the
         // minimum element in ths whole stack
         if (S->element CurrentMiniAddress->element)
         {
            // If the current value is the minimum in the whole stack
            // then S points to itself
            S->CurrentMiniAddress = S;
         }
             else
             {
                 // So this is not the minimum in the whole stack
                 // No worries, TOP is holding the minimum element
                 S->CurrentMiniAddress = TopElement->CurrentMiniAddress;
             }

    }
        Stack.Add(S);
 }

 void Pop()
 {
     if(!Stack.Empty())
     {
        Stack.Pop();
     }  
 }

 int GetMinimum(Stack &stack)
 {
       if(!stack.Empty())
       {
            MyStack *Top  = stack.top();
            // Top always points to the minimumx
            return  Top->CurrentMiniAddress->element;
        }
 }

Ну, из чего ограничения во время выполнения push и pop? Если они не обязаны, являются постоянными, то просто вычисляют минимальное значение в тех двух операциях (делающий их O (n)). Иначе я не вижу, как это может быть сделано с постоянным дополнительным пространством.

public class StackWithMin {
    int min;
    int size;
    int[] data = new int[1024];

    public void push ( int val ) {
        if ( size == 0 ) {
            data[size] = val;
            min = val;
        } else if ( val < min) {
            data[size] = 2 * val - min;
            min = val;

            assert (data[size] < min); 
        } else {
            data[size] = val;
        }

        ++size;

        // check size and grow array
    }

    public int getMin () {
        return min;
    }

    public int pop () {
        --size;

        int val = data[size];

        if ( ( size > 0 ) && ( val < min ) ) {
            int prevMin = min;
            min += min - val;
            return prevMin;
        } else {
            return val;
        }
    }

    public boolean isEmpty () {
        return size == 0;
    }

    public static void main (String...args) {
        StackWithMin stack = new StackWithMin();

        for ( String arg: args ) 
            stack.push( Integer.parseInt( arg ) );

        while ( ! stack.isEmpty() ) {
            int min = stack.getMin();
            int val = stack.pop();

            System.out.println( val + " " + min );
        }

        System.out.println();
    }

}

Это хранит текущий минимум явно, и если минимум изменяется, вместо того, чтобы продвинуть значение, это продвигает значение то же различие другая сторона нового минимума (если минута = 7 и Вы продвигаете 5, это продвигает 3 вместо этого (5-| 7-5 | = 3) и устанавливает минуту на 5; если Вы затем появляетесь 3, когда минута равняется 5, она видит, что вытолканное значение является меньше, чем минута, так инвертирует процедуру для получения 7 в течение новой минуты, то возвраты предыдущая минута). Поскольку любое значение, которое не вызывает изменение текущий минимум, больше, чем текущий минимум, у Вас есть что-то, что может использоваться для дифференциации между значениями, которые изменяют минимум и, которые не делают.

На языках, которые используют целые числа фиксированного размера, Вы одалживаете немного пространства у представления значений, таким образом, оно может потерять значимость, и утверждение перестанет работать. Но иначе, это - постоянное дополнительное пространство, и все операции все еще O (1).

Стеки, которые базируются вместо этого на связанных списках, имеют другие места, можно одолжить немного у, например, в C младший значащий бит прямого указателя, или в Java тип объектов в связанном списке. Для Java это действительно означает, что существует больше пространства, использованного по сравнению с непрерывным стеком, поскольку у Вас есть объект наверху на ссылку:

public class LinkedStackWithMin {
    private static class Link {
        final int value;
        final Link next;

        Link ( int value, Link next ) {
            this.value = value;
            this.next = next;
        }

        int pop ( LinkedStackWithMin stack ) {
            stack.top = next;
            return value;
        }
    }

    private static class MinLink extends Link {
        MinLink ( int value, Link next ) {
            super( value, next );
        }

        int pop ( LinkedStackWithMin stack ) {
            stack.top = next;
            int prevMin = stack.min;
            stack.min = value;
            return prevMin;
        }
    }

    Link top;
    int min;

    public LinkedStackWithMin () {
    }

    public void push ( int val ) {
        if ( ( top == null ) || ( val < min ) ) {
            top = new MinLink(min, top);
            min = val;
        } else {
            top = new Link(val, top);
        }
    }

    public int pop () {
        return top.pop(this);
    }

    public int getMin () {
        return min;
    }

    public boolean isEmpty () {
        return top == null;
    }

В C издержки не там, и можно одолжить lsb прямого указателя:

typedef struct _stack_link stack_with_min;

typedef struct _stack_link stack_link;

struct _stack_link {
    size_t  next;
    int     value;
};

stack_link* get_next ( stack_link* link ) 
{
    return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
}

bool is_min ( stack_link* link )
{
    return ( link -> next & 1 ) ! = 0;
}

void push ( stack_with_min* stack, int value )
{
    stack_link *link = malloc ( sizeof( stack_link ) );

    link -> next = ( size_t ) stack -> next;

    if ( (stack -> next == 0) || ( value == stack -> value ) ) {
        link -> value = stack -> value;
        link -> next |= 1; // mark as min
    } else {
        link -> value = value;
    }

    stack -> next = link;
}

etc.;

Однако ни один из них не действительно O (1). Они больше не требуют пространства на практике, потому что они используют дыры в представлениях чисел, объектов или указателей на этих языках. Но теоретическая машина, которая использовала более компактное представление, потребует, чтобы дополнительный бит был добавлен к тому представлению в каждом случае.

Добавьте поле, чтобы содержать минимальное значение и обновить его во время Pop () и Нажатие (). Тем путем getMinimum () будет O (1), но Pop () и Нажатие () должен будет сделать немного больше работы.

Если минимальное значение будет вытолкано, то Pop () будет O (n), иначе они все еще оба будут O (1). Когда изменение размеров Нажатия () становится O (n) согласно реализации Стека.

Вот быстрая реализация

public sealed class MinStack {
    private int MinimumValue;
    private readonly Stack<int> Stack = new Stack<int>();

    public int GetMinimum() {
        if (IsEmpty) {
            throw new InvalidOperationException("Stack is empty");
        }
        return MinimumValue;
    }

    public int Pop() {
        var value = Stack.Pop();
        if (value == MinimumValue) {
            MinimumValue = Stack.Min();
        }
        return value;
    }

    public void Push(int value) {
        if (IsEmpty || value < MinimumValue) {
            MinimumValue = value;
        }
        Stack.Push(value);
    }

    private bool IsEmpty { get { return Stack.Count() == 0; } }
}