Min Value from Stack

Question

I have a stack which contains some integer data. I want to find out the min value from Stack in O(1) time. Any idea?

PS: There is no ordering (increasing/decreasing) of data in Stack.

Thanks,

Naveen

Answer 1

A stack by definition is push/pop (LIFO) data structure. You can't!

Answer 2

O(n) is the best you're gonna do - you'd have to check each one of the values and compare them to the aggregator minimum, otherwise how would you know you got the lowest?

If you want, you can store the minimum as the values are added, making the pushes more expensive for the benefit of an O(1) read (of the pre-calculated minimum), but that's it.

Answer 3

I am not sure why you expect to do this in constant time for arbitrary length. The best you will be able to do is O(n)

Answer 4

Use two stacks. One is the data, one is the minimums. When you push onto the data stack, push the new minimum onto the minimums stack (the new minimum is the min of the item you're pushing and whatever is currently on the top of the minimums stack), and when you pop, pop off of both stacks (so that the two stacks always have the same number of elements). To find the minimum element, just look at the top of the minimums stack.

Pushing, popping and finding the min value are O(1).

Answer 5

You'll probably want some kind of priority heap if you want to always pop the least element. If you want to pop what was last pushed, but be able to know the order of the elements remaining in the stack, some kind of search tree e.g. red-black will support deletion of an element from an arbitrary position (your stack would have a pointer to the tree node so when you pop you can find it).

If you only need to know the minimum (or max) remaining in the stack then ESRogs' is optimal.

Answer 6

Here is the Python implementation of ESRogs algorithm using lists as stacks:

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]

Here is an example of its usage:

>>> 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: "<"; }

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;

}