Design Problems Collections
/*
Tracking current Maximum Element in a Stack
Given a Stack, keep track of the maximum value in it. The
maximum value may be the top element of the stack,
but once a new element is pushed or an element is pop from
the stack, the maximum element will be now from the rest of the elements.
Examples:
Input : 4 19 7 14 20
Output : Max Values in stack are
4 19 19 19 20
Input : 40 19 7 14 20 5
Output : Max Values in
stack are
40 40 40 40 40
40
Method 2 (Efficient): An efficient approach would be to
maintain an auxiliary stack while pushing element in the main stack.
This auxiliary stack will keep track of the maximum element.
Below is the step by step algorithm to do this:
Create an auxiliary stack, say ‘trackStack’ to keep the track
of maximum element
Push the first element to both mainStack and the trackStack.
Now from the second element, push the element to the main
stack. Compare the element with the top element of the track stack,
if the current element is greater than top of trackStack then
push the current element to trackStack otherwise push the top element
of trackStack again into it.
If we pop an element from the main stack, then pop an element
from the trackStack as well.
Now to compute the maximum of the main stack at any point, we
can simply print the top element of Track stack.
*/
class StackWithMax
{
// main stack
stack<int>
mainStack;
// tack to keep
track of max element
stack<int>
trackStack;
public:
void push(int x)
{
mainStack.push(x);
if
(mainStack.size() == 1)
{
trackStack.push(x);
return;
}
// If current
element is greater than
// the top
element of track stack, push
// the
current element to track stack
// otherwise
push the element at top of
// track
stack again into it.
if (x
> trackStack.top())
trackStack.push(x);
else
trackStack.push(trackStack.top());
}
int
getMax()
{
return
trackStack.top();
}
int pop()
{
mainStack.pop();
trackStack.pop();
}
};
int main()
{
StackWithMax s;
s.push(20);
cout << s.getMax() << endl;
s.push(10);
cout << s.getMax() << endl;
s.push(50);
cout << s.getMax() << endl;
getchar();
return 0;
}
/*
How to implement stack using priority queue or heap?
Solution:
In priority queue, we assign priority to the elements that
are being pushed. A stack requires elements to be processed in
Last in First Out manner. The idea is to associate a count
that determines when it was pushed. This count works as a key for the
priority queue.
So the implementation of stack uses a priority queue of
pairs, with the first element serving as the key.
*/
typedef pair<int,
int> pi;
#include <queue>
class Mystack
{
// cnt is used to
keep track of the number of
//elements in the
stack and also serves as key
//for the
priority queue.
int cnt;
priority_queue<pair<int, int> > pq;
public:
Mystack():cnt(0){}
void push(int n);
void pop();
int top();
bool
isEmpty();
};
// push function increases cnt by 1 and
// inserts this cnt with the original value.
void Mystack::push(int n){
cnt++;
pq.push(pi(cnt, n));
}
// pops element and reduces count.
void Mystack::pop(){
if(pq.empty()){
cout<<"Nothing to pop!!!";}
cnt--;
pq.pop();
}
// returns the top element in the stack using
// cnt as key to determine top(highest priority),
// default comparator for pairs works fine in this case
int Mystack::top(){
pi temp=pq.top();
return
temp.second;
}
// return true if stack is empty
bool Mystack::isEmpty(){
return
pq.empty();
}
int main()
{
Mystack* s=new
Mystack();
s->push(1);
s->push(2);
s->push(3);
while(!s->isEmpty()){
cout<<s->top()<<endl;
s->pop();
}
getchar();
return 0;
}
/*
Find maximum in a stack in O(1) time and O(1) extra space
Given a stack of integers. The task is to design a special
stack such that maximum element can be found in O(1) time and O(1)
extra space.
Examples:
Given Stack :
2
5
1
64 --> Maximum
So Output must be 64 when getMax() is called.
*/
class MaxStack
{
int
maxElem;
stack<int>st;
public:
void push(int item)
{
if
(st.empty())
{
maxElem = item;
st.push(item);
}
else
{
if
(item<st.top())
{
st.push(item);
}
else
{
st.push(2*item -
maxElem);
maxElem = item;
}
}
}
int
getMaxElem()
{
return(maxElem);
}
int top()
{
int
x = st.top();
if
(x > maxElem)
{
return
(maxElem);
}
else
{
return
(x);
}
}
void pop()
{
if
(st.empty())
{
cout<<"Stack is empty"<<endl;
}
else
{
int
x = st.top();
st.pop();
int
max = maxElem;
if
(x > maxElem)
{
maxElem = 2*maxElem - x;
}
}
}
};
int main()
{
MaxStack stack;
stack.push(8);
stack.push(15);
cout<<"maxElem
= "<<stack.getMaxElem()<<endl;
stack.push(4);
cout<<"maxElem
= "<<stack.getMaxElem()<<endl;
stack.push(18);
cout<<"maxElem
= "<<stack.getMaxElem()<<endl;
stack.push(16);
cout<<"maxElem
= "<<stack.getMaxElem()<<endl;
stack.push(23);
cout<<"maxElem
= "<<stack.getMaxElem()<<endl;
cout<<"Performing
pop up operation"<<endl;
stack.pop();
cout<<"maxElem
= "<<stack.getMaxElem()<<endl;
stack.pop();
stack.pop();
cout<<"maxElem1
= "<<stack.getMaxElem()<<endl;
getchar();
return 0;
}
Comments
Post a Comment