Минимальное значение от стека

O (n) - лучшее, что вы собираетесь сделать - вам нужно будет проверить каждое из значений и сравнить их с минимумом агрегатора, иначе как вы узнаете, что получили самый низкий?

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

Стек по определению представляет собой структуру данных push / pop ( LIFO ). Нельзя использовать одну стопку!

Я не уверен, почему вы ожидаете делать это в постоянное время для произвольной длины. Лучшее, что вы сможете сделать, это O (n)

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

Если вам нужно знать только минимальный (или максимальный) остаток в стеке, то ESRogs оптимален.

Вот реализация Python алгоритма ESRogs с использованием списков в виде стеков:

class ConstantStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self,item):
        self.stack.append(item)
        if len(self.min_stack) == 0:
            self.min_stack.append(item)
            return
        # Get the smaller item between the pushed item and the top of the stack
        smallest = min(item,self.min_stack[-1])
        self.min_stack.append(smallest)
    def pop(self):
        self.min_stack.pop()
        return self.stack.pop()
    def min(self):
        # NOTE: min_stack[-1] is equivalent to peek()
        return self.min_stack[-1]

Вот пример его использования:

>>> s = ConstantStack()
>>> s.push(3)
>>> s.push(7)
>>> s.push(6)
>>> s.push(1)
>>> s.min()
1
>>> s.pop()
1
>>> # Now that 1 is gone, 3 is the next smallest
>>> s.min()
3
>>> s.pop()
6
>>> # 6 was popped but 3 still remains the smallest
>>> s.min()
3
>>> s.pop()
7
>>> s.min()
3
>>> s.pop()
3

#define STACKSIZE 50

typedef struct stack
{
    int item[STACKSIZE];
    int top;
}MULSTACKEX;

void InitStack(MULSTACKEX &st)
{
   st.item[STACKSIZE] = 0;
   st.top = -1;
}

void Push(MULSTACKEX &st1, MULSTACKEX &st2, int elem)
{
    if(st1.top == -1)
    {   
        st1.top++;
        st1.item[st1.top] = elem;

        st2.top++;
        st2.item[st2.top] = elem;
    }
    else
    {
        st1.top++;
        st1.item[st1.top] = elem;

        if(elem < st2.item[st2.top])
        {
            st2.top++;
            st2.item[st2.top] = elem;
        }
    }
}

void Display(MULSTACKEX &st1, MULSTACKEX &st2)
{
    cout<<"stack1 elements: "<<endl;
    for(int i = 0; i <= st1.top; i++)
    {
        cout<<st1.item[i]<<"->";
    }

    cout<<endl;
    cout<<"stack2 elements: "<<endl;
    for(int i = 0; i <= st2.top; i++)
    {
        cout<<st2.item[i]<<"->";
    }

}

int Pop(MULSTACKEX &st1, MULSTACKEX &st2)
{
    int elem = 0;
    if(st1.item[st1.top] == st2.item[st2.top])
    {
        elem = st2.item[st2.top];
        st2.top--;

        elem = st1.item[st1.top];
        st1.top--;
    }
    else
    {
        elem = st1.item[st1.top];
        st1.top--;
    }

    return elem;    
}
int FindMin(MULSTACKEX &st2)
{
    int elem = st2.item[st2.top];
    return elem;
}

int _tmain(int argc, _TCHAR* argv[])
{
    MULSTACKEX stack1, stack2;

    InitStack(stack1); 
    InitStack(stack2);


    Push(stack1,stack2,13); 
    Push(stack1,stack2,17);
    Push(stack1,stack2,5);
    Display(stack1,stack2);

    int min_elem1 = FindMin(stack2);
    cout<<"Min element in the list is: "<<min_elem1<<endl<<endl;

    int deletedelem2 = Pop(stack1,stack2);
    cout<<"Pop element from the stack:"<< deletedelem2 <<endl<<endl;
    Display(stack1,stack2);

    cout<<endl<<endl;

    Push(stack1,stack2,19);
    Push(stack1,stack2,8);
    Display(stack1,stack2);

    cout<<endl<<endl;

    int deletedelem1 = Pop(stack1,stack2);
    cout<<"Pop element from the stack:"<< deletedelem1 <<endl<<endl;
    Display(stack1,stack2);

    int min_elem2 = FindMin(stack2);
    cout<<"Min element in the list is: "<<min_elem2<<endl<<endl;

    return 0;
}