# [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
```

More Related questions

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.