Valor mínimo de la pila

Question

Tengo una pila que contiene algunos datos enteros. Quiero saber el valor mínimo de Stack en O (1) vez. ¿Alguna idea?

PD: No se realiza ningún pedido (aumento/disminución) de datos en la pila.

Gracias,

Naveen

Answer 1

Use dos pilas. Uno es los datos, uno son los mínimos. Cuando ingresa a la pila de datos, inserte el nuevo mínimo en la pila de mínimos (el nuevo mínimo es el mínimo del artículo que está presionando y lo que está actualmente en la parte superior de la pila de mínimos), y cuando salga, estallará de ambas pilas (para que las dos pilas siempre tengan la misma cantidad de elementos). Para encontrar el elemento mínimo, solo mira la parte superior de la pila de mínimos.

Empujar, abrir y encontrar el valor mínimo son O (1).

Answer 2

Una pila por definición es push/pop (LIFO) estructura de datos. ¡No puedes usar una sola pila!

Answer 3

O (n) es lo mejor que vas a hacer - deberías verificar cada uno de los valores y compararlos con el mínimo del agregador, de lo contrario, ¿cómo sabrías que obtuviste el más bajo?

Si lo desea, puede almacenar el mínimo a medida que se agregan los valores, haciendo que los empujes sean más caros en beneficio de una lectura O (1) (del mínimo precalculado), pero eso es todo.

Answer 4

No estoy seguro de por qué esperas hacer esto en tiempo constante por longitud arbitraria. Lo mejor que podrá hacer es O (n)

Answer 5

Probablemente querrá algún tipo de priority heap si siempre desea mostrar el elemento menos. Si desea mostrar lo que se presionó por última vez, pero debe saber el orden de los elementos que quedan en la pila, algún tipo de árbol de búsqueda, p. red-black admitirá la eliminación de un elemento desde una posición arbitraria (su pila tendría un puntero al nodo de árbol para que cuando aparezca puede encontrarlo).

Si solo necesita saber el mínimo (o máximo) que queda en la pila, ESRogs 'es óptimo.

Answer 6

Aquí está la implementación de Python del algoritmo ESRogs el uso de listas como pilas:

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] 

Aquí es un ejemplo de su uso:

>>> 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 

Answer 7

#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; 
}