Table of Contents
Problem Statement
“Tracking current Maximum Element in a Stack” states that you are given a stack data structure. Create a function to keep the track of the maximum value in the stack till the current index.
Example
4 19 7 14 20
4 19 19 19 20
Explanation: The maximum values until the current indices are to be printed and they are shown in the above image. As we encounter a number which is greater than the current maximum. The value of current maximum changes.
40 19 7 14 20 5
40 40 40 40 40 40
Naive Method
Algorithm
1. Initialize a stack data structure of integer type. 2. Create an integer variable max and store the element at the top of the stack in it. 3. Whenever we need to find the maximum element, we create a temporary stack to store the elements of main stack. 4. Remove each element from mainStack and store in tmpStack while maintaining the maximum. 4. Print the max.
In naive approach, we keep an extra temporary stack which is used to find the maximum. Every time whenever we need to find the maximum, we traverse all the elements of mainStack. So to traverse the elements we need to pop them out of the main stack and push them into the temporary stack. So that after traversing all the elements we can push them back into the main stack. Thus whenever we need to the maximum until now, the operation costs a linear time complexity of O(N). Thus if we find the maximum until every element, the total time complexity will be O(N^2).
Code
C++ Program for Tracking current Maximum Element in a Stack
#include <bits/stdc++.h>
using namespace std;
class StackWithMax{
stack<int> mainStack;
public:
void push(int x){
mainStack.push(x);
}
int getMax(){
stack<int> tmpStack;
int mx = INT_MIN;
while(!mainStack.empty()){
tmpStack.push(mainStack.top());
mainStack.pop();
mx = max(tmpStack.top(), mx);
}
while(!tmpStack.empty()){
mainStack.push(tmpStack.top());
tmpStack.pop();
}
return mx;
}
int pop(){
mainStack.pop();
}
};
int main(){
StackWithMax s;
s.push(20);
s.push(14);
s.push(7);
s.push(19);
s.push(4);
cout<<s.getMax();
return 0;
}20
Java Program for Tracking current Maximum Element in a Stack
import java.util.*;
class TrackMax{
static class StackWithMax{
static Stack<Integer> mainStack = new Stack<Integer> ();
static void push(int x){
mainStack.push(x);
}
static void getMax(){
int max = mainStack.peek();
while(!mainStack.isEmpty()){
if(max<mainStack.peek()){
max = mainStack.peek();
}
System.out.print(max+" ");
pop();
}
}
static void pop(){
mainStack.pop();
}
};
public static void main(String[] args){
StackWithMax s = new StackWithMax();
s.push(20);
s.push(14);
s.push(7);
s.push(19);
s.push(4);
s.getMax();
}
}20
Complexity Analysis
Time Complexity
O(N), because we traverse all the elements inside the stack per getmax() operation.
Space Complexity
O(N), because we are using a temporary stack to store the elements of the main stack.
Efficient Method
Algorithm
1. Initialize a stack data structure of integer type. 2. Create a class and create two stacks main and temporary of integer type in it. 3. After that, create the function push which accepts an integer variable as it's a parameter. Push/insert the integer variable in the main stack. 4. Check if the size of the main stack is equal to 1, push/insert the integer variable in the temporary stack, and return. 5. If the integer variable is greater than the element at the top of the temporary stack, push/insert the integer variable in the temporary stack. 6. Else push/insert the element at the top of the temporary stack in the temporary stack itself. 7. Similarly, create the function to get the maximum element and return the element at the top of the temporary stack. 8. Also, create the function pop. Pop / remove the element at the top of the temporary stack and the main stack.
Code
C++ Program for Tracking current Maximum Element in a Stack
#include <bits/stdc++.h>
using namespace std;
class StackWithMax{
stack<int> mainStack;
stack<int> trackStack;
public:
void push(int x){
mainStack.push(x);
if(mainStack.size() == 1){
trackStack.push(x);
return;
}
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(4);
cout<<s.getMax()<<" ";
s.push(19);
cout<<s.getMax()<<" ";
s.push(7);
cout<<s.getMax()<<" ";
s.push(14);
cout<<s.getMax()<<" ";
s.push(20);
cout<<s.getMax();
return 0;
}4 19 19 19 20
Java Program for Tracking current Maximum Element in a Stack
import java.util.*;
class TrackMax{
static class StackWithMax{
static Stack<Integer> mainStack = new Stack<Integer> ();
static Stack<Integer> trackStack = new Stack<Integer> ();
static void push(int x){
mainStack.push(x);
if(mainStack.size() == 1){
trackStack.push(x);
return;
}
if(x > trackStack.peek()){
trackStack.push(x);
}
else{
trackStack.push(trackStack.peek());
}
}
static int getMax(){
return trackStack.peek();
}
static void pop(){
mainStack.pop();
trackStack.pop();
}
};
public static void main(String[] args){
StackWithMax s = new StackWithMax();
s.push(4);
System.out.print(s.getMax()+" ");
s.push(19);
System.out.print(s.getMax()+" ");
s.push(7);
System.out.print(s.getMax()+" ");
s.push(14);
System.out.print(s.getMax()+" ");
s.push(20);
System.out.print(s.getMax());
}
}4 19 19 19 20
Complexity Analysis
Time Complexity
O(1), because we are finding the maximum in constant time.
Space Complexity
O(N), here instead of finding the maximum element we are storing the maximum element at the time of input which gave us linear space complexity.