Title:
Design a data structure SpecialStack that supports all stack operations, such as push(), pop(), isEmpty(), isFull() and additional operations getMin(), which should return the smallest element in the SpecialStack. All of these operations of the SpecialStack must be O(1). To implement SpecialStack, you should only use standard stack data structures, and not other data structures such as arrays, lists, etc.
Example:
Consider the following SpecialStack
16 --> TOP
15
29
19
18
When getMin() is called it should
return 15, which is the minimum
element in the current stack.
If we do pop two times on stack, the stack becomes
29 --> TOP
19
18
When getMin() is called, it should
return 18 which is the minimum in
the current stack.Untie:
Two stacks are used: one to store the actual stack elements, and one to store the minimum values as a secondary stack. The way to do this is to do push() and pop() so that the top of the secondary stack is always the smallest. Let’s see how the push() and pop() operations work.
Push(int x) // inserts element x into the special stack
1) Push x into the first stack (the stack with the actual elements)
2) Compare x to the top element of the second stack (helper stack). Make the top element y.
…..a) If x is less than y, then push x into the secondary stack.
…..b) If x is greater than y, then push y into the helper stack.
int pop() // Remove an element from a special stack and return the deleted element
1) Pop the top element from the secondary stack.
2) Pop the top element from the actual stack and return it.
Step 1 must be performed to ensure that the secondary stack is also updated for future operations.
int getMin()// returns the smallest element in a special stack
1) Return to the top element of the helper stack.
We can see that all of the above operations are O(1).
Let’s look at an example. Let’s assume that both stacks are initially empty, and that 18, 19, 29, 15, and 16 are inserted into the SpecialStack.
When we insert 18, both stacks change to following.
Actual Stack
18 <--- top
Auxiliary Stack
18 <---- top
When 19 is inserted, both stacks change to following.
Actual Stack
19 <--- top
18
Auxiliary Stack
18 <---- top
18
When 29 is inserted, both stacks change to following.
Actual Stack
29 <--- top
19
18
Auxiliary Stack
18 <---- top
18
18
When 15 is inserted, both stacks change to following.
Actual Stack
15 <--- top
29
19
18
Auxiliary Stack
15 <---- top
18
18
18
When 16 is inserted, both stacks change to following.
Actual Stack
16 <--- top
15
29
19
18
Auxiliary Stack
15 <---- top
15
18
18
18Here’s an implementation of the SpecialStack class. In the following implementation, SpecialStack inherits from Stack and has a Stack object min as a secondary stack.
C++
#include <iostream>
#include <stdlib.h>
using namespace std;
/* A simple stack class with
basic stack funtionalities */
class Stack {
private :
static const int max = 100;
int arr[max];
int top;
public :
Stack() { top = -1; }
bool isEmpty();
bool isFull();
int pop();
void push( int x);
};
/* Stack's member method to check
if the stack is iempty */
bool Stack::isEmpty()
{
if (top == -1)
return true ;
return false ;
}
/* Stack's member method to check
if the stack is full */
bool Stack::isFull()
{
if (top == max - 1)
return true ;
return false ;
}
/* Stack's member method to remove
an element from it */
int Stack::pop()
{
if (isEmpty()) {
cout <<"Stack Underflow" ;
abort ();
}
int x = arr[top];
top--;
return x;
}
/* Stack's member method to insert
an element to it */
void Stack::push( int x)
{
if (isFull()) {
cout <<"Stack Overflow" ;
abort ();
}
top++;
arr[top] = x;
}
/* A class that supports all the stack
operations and one additional
operation getMin() that returns the
minimum element from stack at
any time. This class inherits from
the stack class and uses an
auxiliarry stack that holds minimum
elements */
class SpecialStack : public Stack {
Stack min;
public :
int pop();
void push( int x);
int getMin();
};
/* SpecialStack's member method to insert
an element to it. This method
makes sure that the min stack is also
updated with appropriate minimum
values */
void SpecialStack::push( int x)
{
if (isEmpty() == true ) {
Stack::push(x);
min.push(x);
}
else {
Stack::push(x);
int y = min.pop();
min.push(y);
if (x <y)
min.push(x);
else
min.push(y);
}
}
/* SpecialStack's member method to
remove an element from it. This method
removes top element from min stack also. */
int SpecialStack::pop()
{
int x = Stack::pop();
min.pop();
return x;
}
/* SpecialStack's member method to get
minimum element from it. */
int SpecialStack::getMin()
{
int x = min.pop();
min.push(x);
return x;
}
/* Driver program to test SpecialStack
methods */
int main()
{
SpecialStack s;
s.push(10);
s.push(20);
s.push(30);
cout <<s.getMin() <<endl;
s.push(5);
cout <<s.getMin();
return 0;
}Java
//Java implementation of SpecialStack
//Note : here we use Stack class for
//Stack implementation
import java.util.Stack;
/* A class that supports all the
stack operations and one additional
operation getMin() that returns
the minimum element from stack at
any time. This class inherits from
the stack class and uses an
auxiliarry stack that holds minimum
elements */
class SpecialStack extends Stack<Integer> {
Stack<Integer> min = new Stack<>();
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
void push( int x)
{
if (isEmpty() == true ) {
super .push(x);
min.push(x);
}
else {
super .push(x);
int y = min.pop();
min.push(y);
if (x <y)
min.push(x);
else
min.push(y);
}
}
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
public Integer pop()
{
int x = super .pop();
min.pop();
return x;
}
/* SpecialStack's member method to get
minimum element from it. */
int getMin()
{
int x = min.pop();
min.push(x);
return x;
}
/* Driver program to test SpecialStack
methods */
public static void main(String[] args)
{
SpecialStack s = new SpecialStack();
s.push( 10 );
s.push( 20 );
s.push( 30 );
System.out.println(s.getMin());
s.push( 5 );
System.out.println(s.getMin());
}
}
//This code is contributed by Sumit GhoshPython3
# Python3 program for the
# above approach
# A simple stack class with
# basic stack funtionalities
class stack:
def __init__( self ):
self .array = []
self .top = - 1
self . max = 100
# Stack's member method to check
# if the stack is iempty
def isEmpty( self ):
if self .top = = - 1 :
return True
else :
return False
# Stack's member method to check
# if the stack is full
def isFull( self ):
if self .top = = self . max - 1 :
return True
else :
return False
# Stack's member method to
# insert an element to it
def push( self , data):
if self .isFull():
print ( 'Stack OverFlow' )
return
else :
self .top + = 1
self .array.append(data)
# Stack's member method to
# remove an element from it
def pop( self ):
if self .isEmpty():
print ( 'Stack UnderFlow' )
return
else :
self .top - = 1
return self .array.pop()
# A class that supports all the stack
# operations and one additional
# operation getMin() that returns the
# minimum element from stack at
# any time. This class inherits from
# the stack class and uses an
# auxiliarry stack that holds
# minimum elements
class SpecialStack(stack):
def __init__( self ):
super ().__init__()
self . Min = stack()
# SpecialStack's member method to
# insert an element to it. This method
# makes sure that the min stack is also
# updated with appropriate minimum
# values
def push( self , x):
if self .isEmpty():
super ().push(x)
self . Min .push(x)
else :
super ().push(x)
y = self . Min .pop()
self . Min .push(y)
if x <= y:
self . Min .push(x)
else :
self . Min .push(y)
# SpecialStack's member method to
# remove an element from it. This
# method removes top element from
# min stack also.
def pop( self ):
x = super ().pop()
self . Min .pop()
return x
# SpecialStack's member method
# to get minimum element from it.
def getmin( self ):
x = self . Min .pop()
self . Min .push(x)
return x
# Driver code
if __name__ = = '__main__' :
s = SpecialStack()
s.push( 10 )
s.push( 20 )
s.push( 30 )
print (s.getmin())
s.push( 5 )
print (s.getmin())
# This code is contributed by rachitkatiyar99The output is as follows
10
5Complexity Analysis:
- Time Complexity:
- For insert operation: O(1) (due to the time it takes to insert “push” into the stack)
- For delete operation: O(1) (due to the time it takes to delete “pop” in the stack)
- For the Get Min operation: O(1) (because the top of the helper stack we use is the smallest element)
- Auxiliary space: O(n).
Use the secondary stack to store values.
Space-optimized version
The above methods can be optimized. We can limit the number of elements in the helper stack. We can only push if the incoming element of the main stack is less than or equal to the top of the secondary stack. Similarly, during the ejection process, if the pop-up element is equal to the top of the secondary stack, remove the top element of the secondary stack. Here are the modified implementations of push() and pop().
C++
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
void SpecialStack::push( int x)
{
if (isEmpty() == true ) {
Stack::push(x);
min.push(x);
}
else {
Stack::push(x);
int y = min.pop();
min.push(y);
/* push only when the incoming element
of main stack is smaller
than or equal to top of auxiliary stack */
if (x <= y)
min.push(x);
}
}
/* SpecialStack's member method to
remove an element from it. This method
removes top element from min stack also. */
int SpecialStack::pop()
{
int x = Stack::pop();
int y = min.pop();
/* Push the popped element y back
only if it is not equal to x */
if (y != x)
min.push(y);
return x;
}Java
/* SpecialStack's member method to
insert an element to it. This method
makes sure that the min stack is
also updated with appropriate minimum
values */
void push( int x)
{
if (isEmpty() == true ) {
super .push(x);
min.push(x);
}
else {
super .push(x);
int y = min.pop();
min.push(y);
/* push only when the incoming
element of main stack is smaller
than or equal to top of auxiliary stack */
if (x <= y)
min.push(x);
}
}
/* SpecialStack's member method to
remove an element from it. This method
removes top element from min stack also. */
public Integer pop()
{
int x = super .pop();
int y = min.pop();
/* Push the popped element y back
only if it is not equal to x */
if (y != x)
min.push(y);
return x;
}
//This code is contributed by Sumit GhoshComplexity Analysis:
- Time Complexity:
- For insert operation: O(1) (due to the time it takes to insert “push” into the stack)
- For delete operation: O(1) (due to the time it takes to delete “pop” in the stack)
- For the Get Min operation: O(1) (because the top of the helper we use is the smallest element)
- Auxiliary space: O(n).
The worst-case complexity is the same as above, but in other cases, it takes up a bit less space than the above method because repetition is ignored.
Design a stack that supports O(1) time and O(1) extra space for getMin().
If you find the above code incorrect, or find other solutions to the same problem, please write a comment.
