by Stack is a data structure used for storing collection of data where order in which data is arriving is important. In Stack, insertion and deletion both happened from the same end which is known as “Top”.
The data which is arrived last will be deleted first in Stack. This data ordering is called as Last in First out or LIFO. Before going ahead have a look into Stack basics and Stack Implementation.
Get Minimum value from the Stack
In this case, we need to find out the minimum value stored in the Stack and return the same. After popping elements from the stack, minimum value stored in the stack might change and hence new minimum should be returned.
Here we are going to look into the program to return Minimum value from Stack in O(1) time complexity.
Get Minimum value from the Stack in O(1) time complexity
In this case, getMinimum function time complexity should be O(1). In order to do so, we need one more stack which maintains the minimum value stored in the stack.
Algorithm
- PUSH operation will push value into main stack. In minimum stack, push either the new value or current top element whichever is lower. In this way, minimum stack top element always contain minimum value stored in the main stack.
- POP operation will pop element from both main and minimum stack.
- TOP element from minimum Stack will contain the minimum value stored in the main Stack.
Let’s take an example to analyze the above algorithm.
| Main Stack | Minimum Stack |
|---|---|
| top ——> 1 | top ——> 1 |
| 12 | 2 |
| 2 | 2 |
| 9 | 3 |
| 3 | 3 |
| 7 | 4 |
| 4 | 4 |
| 8 | 5 |
| 5 | 5 |
Few of the functions used below are explained in Stack Implementation. Refer those before going ahead.
Let’s look into the sample code.
class StackMinimum
{
private:
Stack m_value;
Stack m_min;
public:
StackMinimum (int size): m_value (size),
m_min (size)
{}
bool push (int value)
{
if (!m_value.push (value))
return false;
if (!m_min.isEmpty() && m_min.atTop () < value)
{
return m_min.push (m_min.atTop ());
}
else
{
return m_min.push (value);
}
}
int pop ()
{
m_min.pop ();
return m_value.pop ();
}
int getMinimum ()
{
if (m_min.isEmpty ())
{
cout << "Stack is empty returning error: ";
return -1;
}
return m_min.atTop ();
}
int entries ()
{
return m_value.entries ();
}
void size ()
{
cout << "Main Stack size: " << m_value.entries () << endl;
cout << "Minimum Stack size: " << m_min.entries () << endl;
}
};
Let’s define a main function to use above methods.
int main ()
{
StackMinimum s (20);
s.push (5);
s.push (8);
s.push (4);
s.push (7);
s.push (3);
s.push (9);
s.push (2);
s.push (12);
s.push (1);
s.size ();
cout << "At the begining minimum value is: " << s.getMinimum () << endl;
while (s.entries () > 0)
{
cout << "After Poping element: " << s.pop () << " New minimum value is: " << s.getMinimum () << endl;
}
}
Let’s analyze the output of this main function.
Main Stack size: 9
Minimum Stack size: 9
At the begining minimum value is: 1
After Poping element: 1 New minimum value is: 2
After Poping element: 12 New minimum value is: 2
After Poping element: 2 New minimum value is: 3
After Poping element: 9 New minimum value is: 3
After Poping element: 3 New minimum value is: 4
After Poping element: 7 New minimum value is: 4
After Poping element: 4 New minimum value is: 5
After Poping element: 8 New minimum value is: 5
After Poping element: 5 New minimum value is: Stack is empty returning error: -1
As you can see here, Main Stack and Minimum Stack size are always same. We can optimize this behavior to reduce the size of Minimum Stack. Let’s look into the optimized algorithm.
Get Minimum value from the Stack in O(1) time complexity and O(1) space complexity
In this case, getMinimum function time complexity should be O(1) and space complexity should be O(1). In order to do so, we need one more stack which maintains the minimum value stored in the stack.
Algorithm
- PUSH operation will push value into main stack. In minimum stack, push only if new value is equal to or lower than current top element. In this way, minimum stack top element always contain minimum value stored in the main stack.
- POP operation will pop element from main Stack. Pop element from minimum stack if popped element from main stack is equal to top element of minimum stack.
- TOP element from minimum Stack will contain the minimum value stored in the main Stack.
Let’s take an example to analyze the above algorithm.
| Main Stack | Minimum Stack |
|---|---|
| top ——> 1 | top ——> 1 |
| 12 | |
| 2 | 2 |
| 9 | |
| 3 | 3 |
| 7 | |
| 4 | 4 |
| 8 | |
| 5 | 5 |
Few of the functions used below are explained in Stack Implementation. Refer those before going ahead.
Let’s look into the sample code.
class StackMinimum
{
private:
Stack m_value;
Stack m_min;
public:
StackMinimum (int size): m_value (size),
m_min (size)
{}
int getMinimum ()
{
if (m_min.isEmpty ())
{
cout << "Stack is empty returning error: ";
return -1;
}
return m_min.atTop ();
}
int entries ()
{
return m_value.entries ();
}
bool push (int value)
{
if (!m_value.push (value))
return false;
if (m_min.isEmpty() || m_min.atTop () >= value)
{
return m_min.push (value);
}
}
int pop ()
{
if (m_value.atTop () == m_min.atTop ())
{
m_min.pop ();
}
return m_value.pop ();
}
void size ()
{
cout << "Main Stack size: " << m_value.entries () << endl;
cout << "Minimum Stack size: " << m_min.entries () << endl;
}
};
Let’s define a main function to use above methods.
int main ()
{
StackMinimum s (20);
s.push (5);
s.push (8);
s.push (4);
s.push (7);
s.push (3);
s.push (9);
s.push (2);
s.push (12);
s.push (1);
s.size ();
cout << "At the begining minimum value is: " << s.getMinimum () << endl;
while (s.entries () > 0)
{
cout << "After Poping element: " << s.pop () << " New minimum value is: " << s.getMinimum () << endl;
}
}
Let’s analyze the output of this main function.
Main Stack size: 9
Minimum Stack size: 5
At the begining minimum value is: 1
After Poping element: 1 New minimum value is: 2
After Poping element: 12 New minimum value is: 2
After Poping element: 2 New minimum value is: 3
After Poping element: 9 New minimum value is: 3
After Poping element: 3 New minimum value is: 4
After Poping element: 7 New minimum value is: 4
After Poping element: 4 New minimum value is: 5
After Poping element: 8 New minimum value is: 5
After Poping element: 5 New minimum value is: Stack is empty returning error: -1
