[ACCEPTED]-Min Value from Stack-data-structures

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

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

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

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

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

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

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

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

Here is the Python implementation of ESRogs 2 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 1 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

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

0

Instead of pushing 1 value, we push a pair 10 of numbers. first element will be element 9 that you want to push, second element would 8 be minimum element of the stack and we should 7 keep track of the minimum element. (element,minOfStack)

let 6 say you have an empty array. when first 5 you push data to the stack,firs element 4 is also minumum value.

 data=[(1,1)]

then you add value 3 2. you check the minimim value of the stack 2 which is 1, 1<2, so you push (2,1) to 1 the array

data=[(1,1),(2,1)]

Here is the python implementation

class StackTrackingMin:
    def __init__(self):
        self._data=[]
    def push(self,x:int)->None:
        currentMin=self.getMin()
        if currentMin==None or currentMin>x:
            currentMin=x
        self._data.append((x,currentMin))
    def pop(self)->None:
        self._data.pop() # pop does not return anything
    def top(self)->int:
        return self._date[-1] if self._data else None
    def getMin(self)->int:
        return self._data[-1][1] if self._data else None