Posted on by Kalkicode
Code Stack

# Tracking present maximum element in a stack

The problem of "Tracking the present maximum element in a stack" involves designing a stack data structure that keeps track of the maximum element in the stack at any given time. In other words, we need to implement a special stack that allows us to efficiently find the maximum element in the stack without removing it.

## Problem Statement

Design a stack that supports the following operations efficiently:

1. `push(element)`: Add an element to the stack.
2. `pop()`: Remove the top element from the stack.
3. `peek()`: Get the top element from the stack without removing it.
4. `maxElement()`: Get the maximum element present in the stack at any given time.

## Example

Consider the following operations on the stack:

``````push(6)
push(4)
push(7)
push(3)
push(13)
push(8)
maxElement() => Should return 13
pop()
maxElement() => Should return 13
pop()
maxElement() => Should return 7
``````

## Idea to Solve the Problem

To track the maximum element in a stack, we need to maintain two separate stacks: the main stack and the tracker stack. The main stack will hold the actual elements, and the tracker stack will keep track of the maximum element at each position in the main stack.

When we add an element to the stack using the `push` operation, we also compare it with the top element of the tracker stack. If the new element is greater, we add it to the tracker stack. Otherwise, we add a copy of the top element from the tracker stack to the tracker stack. This way, the tracker stack always has the maximum element at the top corresponding to the main stack's top.

When we remove an element from the main stack using the `pop` operation, we also remove the top element from the tracker stack to keep them in sync.

## Algorithm

1. Define two custom stack data structures: `MyStack` for the main stack and `TrackerStack` for the tracker stack.
2. In the `push` operation of `MyStack`, add the element to the main stack and compare it with the top element of the tracker stack. If the new element is greater, push it to the tracker stack; otherwise, push a copy of the top element from the tracker stack to the tracker stack.
3. In the `pop` operation of `MyStack`, remove the top element from both the main stack and the tracker stack.
4. In the `peek` operation of `MyStack`, return the top element of the main stack without removing it.
5. In the `maxElement` operation of `TrackerStack`, return the top element of the tracker stack, which represents the maximum element in the main stack at the current position.

## Pseudocode

``````Class StackNode:
Integer element
StackNode next

Class MyStack:
StackNode top
Integer size
Function push(element):
Create a new StackNode with the given element and set its next to top
Set top to the new node
Increment size

Function pop():
If the stack is not empty:
Set top to top.next
Decrement size

Function peek():

Class TrackerStack:
MyStack mainStack
MyStack trackerStack
Function push(element):
Push the element to mainStack
If the tracker stack is not empty and element > trackerStack.peek():
Push the element to trackerStack
Else:
Push trackerStack.peek() to trackerStack

Function pop():
If the mainStack is not empty:
Pop an element from mainStack
Pop an element from trackerStack

Function maxElement():
If the trackerStack is not empty, return trackerStack.peek()

``````

## Code Solution

``````// C program
// Tracking the maximum element in a stack
#include <stdio.h>
#include <stdlib.h>

// Define stack node
struct StackNode
{
int element;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};
struct MyStack *tracker = NULL;
struct MyStack *newStack()
{
// Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
// Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
}
//Create a new node of stack
struct StackNode *newNode(int element, struct StackNode *next)
{
//Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->element = element;
node->next = next;
}
return node;
}
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{
stack->top = newNode(element, stack->top);
if (tracker->top != NULL && tracker->top->element > element)
{
// When previous element is largest
tracker->top = newNode(tracker->top->element, tracker->top);
}
else
{
tracker->top = newNode(element, tracker->top);
}
// Change size
stack->size++;
tracker->size++;
}
struct StackNode *peek(struct MyStack *stack)
{
return stack->top;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (isEmpty(stack) == 0)
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
printf(" Pop Element : %d\n", temp->element);
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
if (isEmpty(tracker) == 0)
{
struct StackNode *temp = tracker->top;
// Change top element of stack
tracker->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
tracker->size--;
}
}
void maxElemenet(struct MyStack *stack)
{
if (stack->top != NULL && tracker->top != NULL)
{
// Display top element of current stack and max element in current instant
printf(" Stack Top : %d  Max is : %d \n", stack->top->element, tracker->top->element);
}
}
int main()
{
tracker = newStack();
struct MyStack *stack = newStack();
push(stack, 6);
push(stack, 4);
push(stack, 7);
push(stack, 3);
push(stack, 13);
push(stack, 8);
maxElemenet(stack);
pop(stack);
maxElemenet(stack);
pop(stack);
maxElemenet(stack);
return 0;
}``````

#### Output

`````` Stack Top : 8  Max is : 13
Pop Element : 8
Stack Top : 13  Max is : 13
Pop Element : 13
Stack Top : 3  Max is : 7``````
``````/*
Java Program
Tracking the maximum element in a stack
*/
// Define stack node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public int peek()
{
return this.top.element;
}
}
public class Tracking
{
public MyStack stack;
public MyStack tracker;
public Tracking()
{
this.stack = new MyStack();
this.tracker = new MyStack();
}
// Handles the request of adding a element into stack
{
// add node in normal stack
this.stack.push(element);
if (this.tracker.isEmpty() == false && this.tracker.peek() > element)
{
this.tracker.push(this.tracker.peek());
}
else
{
this.tracker.push(element);
}
}
public void remove()
{
if (this.stack.isEmpty() == false)
{
System.out.print(" Pop Element : " + this.stack.peek() + "\n");
this.stack.pop();
}
if (this.tracker.isEmpty() == false)
{
this.tracker.pop();
}
}
public void maxElemenet()
{
if (this.stack.top != null && this.tracker.top != null)
{
// Display top element of current stack and max element in current instant
System.out.print(" Stack Top : " + this.stack.peek() + " Max is : " + this.tracker.peek() + " \n");
}
}
public static void main(String[] args)
{
Tracking obj = new Tracking();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
}
}``````

#### Output

`````` Stack Top : 8 Max is : 13
Pop Element : 8
Stack Top : 13 Max is : 13
Pop Element : 13
Stack Top : 3 Max is : 7``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Tracking the maximum element in a stack
*/
// Define stack node
class StackNode
{
public: int element;
StackNode *next;
StackNode(int element, StackNode *next)
{
this->element = element;
this->next = next;
}
};
// Define a custom stack
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
temp = NULL;
this->size--;
}
}
int peek()
{
return this->top->element;
}
};
class Tracking
{
public: MyStack *stack;
MyStack *tracker;
Tracking()
{
this->stack = new MyStack();
this->tracker = new MyStack();
}
// Handles the request of adding a element into stack
{
// Add node in normal stack
this->stack->push(element);

if (this->tracker->isEmpty() == false && this->tracker->peek() > element)
{
this->tracker->push(this->tracker->peek());
}
else
{
this->tracker->push(element);
}
}
void remove()
{
if (this->stack->isEmpty() == false)
{
cout << " Pop Element : " << this->stack->peek() << "\n";
this->stack->pop();
}
if (this->tracker->isEmpty() == false)
{
this->tracker->pop();
}
}
void maxElemenet()
{
if (this->stack->top != NULL && this->tracker->top != NULL)
{
// Display top element of current stack and max element in current instant
cout << " Stack Top : " << this->stack->peek() << " Max is : " << this->tracker->peek() << " \n";
}
}
};
int main()
{
Tracking obj = Tracking();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
return 0;
}``````

#### Output

`````` Stack Top : 8 Max is : 13
Pop Element : 8
Stack Top : 13 Max is : 13
Pop Element : 13
Stack Top : 3 Max is : 7``````
``````// Include namespace system
using System;
/*
C# Program
Tracking the maximum element in a stack
*/
// Define stack node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public int peek()
{
return this.top.element;
}
}
public class Tracking
{
public MyStack stack;
public MyStack tracker;
public Tracking()
{
this.stack = new MyStack();
this.tracker = new MyStack();
}
// Handles the request of adding a element into stack
{
// add element in normal stack
this.stack.push(element);
// add element in tracker stack
if (this.tracker.isEmpty() == false && this.tracker.peek() > element)
{
this.tracker.push(this.tracker.peek());
}
else
{
this.tracker.push(element);
}
}
public void remove()
{
if (this.stack.isEmpty() == false)
{
Console.Write(" Pop Element : " + this.stack.peek() + "\n");
this.stack.pop();
}
if (this.tracker.isEmpty() == false)
{
this.tracker.pop();
}
}
public void maxElemenet()
{
if (this.stack.top != null && this.tracker.top != null)
{
// Display top element of current stack and max element in current instant
Console.Write(" Stack Top : " + this.stack.peek() + " Max is : " + this.tracker.peek() + " \n");
}
}
public static void Main(String[] args)
{
Tracking obj = new Tracking();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
}
}``````

#### Output

`````` Stack Top : 8 Max is : 13
Pop Element : 8
Stack Top : 13 Max is : 13
Pop Element : 13
Stack Top : 3 Max is : 7``````
``````<?php
/*
Php Program
Tracking the maximum element in a stack
*/
// Define stack node
class StackNode
{
public \$element;
public \$next;

function __construct(\$element, \$next)
{
\$this->element = \$element;
\$this->next = \$next;
}
}
// Define a custom stack
class MyStack
{
public \$top;
public \$size;

function __construct()
{
//Set node values
\$this->top = null;
\$this->size = 0;
}
// Add node at the top of stack
public	function push(\$element)
{
\$this->top = new StackNode(\$element, \$this->top);
\$this->size++;
}
public	function isEmpty()
{
if (\$this->size > 0 && \$this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public	function pop()
{
if (\$this->size > 0 && \$this->top != null)
{
\$temp = \$this->top;
// Change top element of stack
\$this->top = \$temp->next;
// remove previous top
\$temp = null;
\$this->size--;
}
}
public	function peek()
{
return \$this->top->element;
}
}
class Tracking
{
public \$stack;
public \$tracker;

function __construct()
{
\$this->stack = new MyStack();
\$this->tracker = new MyStack();
}
// Handles the request of adding a element into stack
{
// add element in normal stack
\$this->stack->push(\$element);
// add element in tracker stack
if (\$this->tracker->isEmpty() == false && \$this->tracker->peek() > \$element)
{
\$this->tracker->push(\$this->tracker->peek());
}
else
{
\$this->tracker->push(\$element);
}
}
public	function remove()
{
if (\$this->stack->isEmpty() == false)
{
echo " Pop Element : ". \$this->stack->peek() ."\n";
\$this->stack->pop();
}
if (\$this->tracker->isEmpty() == false)
{
\$this->tracker->pop();
}
}
public	function maxElemenet()
{
if (\$this->stack->top != null && \$this->tracker->top != null)
{
// Display top element of current stack and max element in current instant
echo " Stack Top : ". \$this->stack->peek() ." Max is : ". \$this->tracker->peek() ." \n";
}
}
}

function main()
{
\$obj = new Tracking();
\$obj->maxElemenet();
\$obj->remove();
\$obj->maxElemenet();
\$obj->remove();
\$obj->maxElemenet();
}
main();``````

#### Output

`````` Stack Top : 8 Max is : 13
Pop Element : 8
Stack Top : 13 Max is : 13
Pop Element : 13
Stack Top : 3 Max is : 7``````
``````/*
Node Js Program
Tracking the maximum element in a stack
*/
// Define stack node
class StackNode
{
constructor(element, next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
peek()
{
return this.top.element;
}
}
class Tracking
{
constructor()
{
this.stack = new MyStack();
this.tracker = new MyStack();
}
// Handles the request of adding a element into stack
{
// add element in normal stack
this.stack.push(element);
// add element in tracker stack
if (this.tracker.isEmpty() == false && this.tracker.peek() > element)
{
this.tracker.push(this.tracker.peek());
}
else
{
this.tracker.push(element);
}
}
remove()
{
if (this.stack.isEmpty() == false)
{
process.stdout.write(" Pop Element : " + this.stack.peek() + "\n");
this.stack.pop();
}
if (this.tracker.isEmpty() == false)
{
this.tracker.pop();
}
}
maxElemenet()
{
if (this.stack.top != null && this.tracker.top != null)
{
// Display top element of current stack and max element in current instant
process.stdout.write(" Stack Top : " + this.stack.peek() + " Max is : " + this.tracker.peek() + " \n");
}
}
}

function main()
{
var obj = new Tracking();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
}
main();``````

#### Output

`````` Stack Top : 8 Max is : 13
Pop Element : 8
Stack Top : 13 Max is : 13
Pop Element : 13
Stack Top : 3 Max is : 7``````
``````#  Python 3 Program
#  Tracking the maximum element in a stack

#  Define stack node
class StackNode :

def __init__(self, element, next) :
self.element = element
self.next = next

#  Define a custom stack
class MyStack :

def __init__(self) :
# Set node values
self.top = None
self.size = 0

#  Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1

def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True

#  Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = None
self.size -= 1

def peek(self) :
return self.top.element

class Tracking :

def __init__(self) :
self.stack = MyStack()
self.tracker = MyStack()

#  Handles the request of adding a element into stack
#  add element in normal stack
self.stack.push(element)
#  add element in tracker stack
if (self.tracker.isEmpty() == False and self.tracker.peek() > element) :
self.tracker.push(self.tracker.peek())
else :
self.tracker.push(element)

def remove(self) :
if (self.stack.isEmpty() == False) :
print(" Pop Element : ", self.stack.peek() )
self.stack.pop()

if (self.tracker.isEmpty() == False) :
self.tracker.pop()

def maxElemenet(self) :
if (self.stack.top != None and self.tracker.top != None) :
#  Display top element of current stack and max element in current instant
print(" Stack Top : ", self.stack.peek() ," Max is : ", self.tracker.peek() ," ")

def main() :
obj = Tracking()
obj.maxElemenet()
obj.remove()
obj.maxElemenet()
obj.remove()
obj.maxElemenet()

if __name__ == "__main__": main()``````

#### Output

`````` Stack Top :  8  Max is :  13
Pop Element :  8
Stack Top :  13  Max is :  13
Pop Element :  13
Stack Top :  3  Max is :  7``````
``````#  Ruby Program
#  Tracking the maximum element in a stack

#  Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_accessor :element, :next

def initialize(element, nextNode)
self.element = element
self.next = nextNode
end

end

#  Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_accessor :top, :size

def initialize()
# Set node values
self.top = nil
self.size = 0
end

#  Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end

def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end

end

#  Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = nil
self.size -= 1
end

end

def peek()
return self.top.element
end

end

class Tracking
# Define the accessor and reader of class Tracking
attr_accessor :stack, :tracker

def initialize()
self.stack = MyStack.new()
self.tracker = MyStack.new()
end

#  Handles the request of adding a element into stack
#  add element in normal stack
self.stack.push(element)
#  add element in tracker stack
if (self.tracker.isEmpty() == false && self.tracker.peek() > element)
self.tracker.push(self.tracker.peek())
else
self.tracker.push(element)
end

end

def remove()
if (self.stack.isEmpty() == false)
print(" Pop Element : ", self.stack.peek() ,"\n")
self.stack.pop()
end

if (self.tracker.isEmpty() == false)
self.tracker.pop()
end

end

def maxElemenet()
if (self.stack.top != nil && self.tracker.top != nil)
#  Display top element of current stack and max element in current instant
print(" Stack Top : ", self.stack.peek() ," Max is : ", self.tracker.peek() ," \n")
end

end

end

def main()
obj = Tracking.new()
obj.maxElemenet()
obj.remove()
obj.maxElemenet()
obj.remove()
obj.maxElemenet()
end

main()``````

#### Output

`````` Stack Top : 8 Max is : 13
Pop Element : 8
Stack Top : 13 Max is : 13
Pop Element : 13
Stack Top : 3 Max is : 7
``````
``````/*
Scala Program
Tracking the maximum element in a stack
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode)
{
}
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: Int): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
def peek(): Int = {
return this.top.element;
}
}
class Tracking(var stack: MyStack , var tracker: MyStack)
{
def this()
{
this(new MyStack(), new MyStack());
}
// Handles the request of adding a element into stack
def add(element: Int): Unit = {
// add element in normal stack
this.stack.push(element);
// add element in tracker stack
if (this.tracker.isEmpty() == false && this.tracker.peek() > element)
{
this.tracker.push(this.tracker.peek());
}
else
{
this.tracker.push(element);
}
}
def remove(): Unit = {
if (this.stack.isEmpty() == false)
{
print(" Pop Element : " + this.stack.peek() + "\n");
this.stack.pop();
}
if (this.tracker.isEmpty() == false)
{
this.tracker.pop();
}
}
def maxElemenet(): Unit = {
if (this.stack.top != null && this.tracker.top != null)
{
// Display top element of current stack and max element in current instant
print(" Stack Top : " + this.stack.peek() + " Max is : " + this.tracker.peek() + " \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Tracking = new Tracking();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
}
}``````

#### Output

`````` Stack Top : 8 Max is : 13
Pop Element : 8
Stack Top : 13 Max is : 13
Pop Element : 13
Stack Top : 3 Max is : 7``````
``````/*
Swift 4 Program
Tracking the maximum element in a stack
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int, _ next: StackNode? )
{
self.element = element;
self.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: Int)
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
func peek()->Int
{
return self.top!.element;
}
}
class Tracking
{
var stack: MyStack? ;
var tracker: MyStack? ;
init()
{
self.stack = MyStack();
self.tracker = MyStack();
}
// Handles the request of adding a element into stack
{
// add element in normal stack
self.stack!.push(element);
// add element in tracker stack
if (self.tracker!.isEmpty() == false && self.tracker!.peek() > element)
{
self.tracker!.push(self.tracker!.peek());
}
else
{
self.tracker!.push(element);
}
}
func remove()
{
if (self.stack!.isEmpty() == false)
{
print(" Pop Element : ", self.stack!.peek() );
self.stack!.pop();
}
if (self.tracker!.isEmpty() == false)
{
self.tracker!.pop();
}
}
func maxElemenet()
{
if (self.stack!.top != nil && self.tracker!.top != nil)
{
// Display top element of current stack and max element in current instant
print(" Stack Top : ", self.stack!.peek() ," Max is : ", self.tracker!.peek() ," ");
}
}
}
func main()
{
let obj: Tracking = Tracking();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
}
main();``````

#### Output

`````` Stack Top :  8  Max is :  13
Pop Element :  8
Stack Top :  13  Max is :  13
Pop Element :  13
Stack Top :  3  Max is :  7``````
``````/*
Kotlin Program
Tracking the maximum element in a stack
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int, next: StackNode ? )
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: Int): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size>0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size>0 && this.top != null)
{
var temp: StackNode? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
fun peek(): Int
{
return  this.top!!.element;
}
}
class Tracking
{
var stack: MyStack  ;
var tracker: MyStack  ;
constructor()
{
this.stack = MyStack();
this.tracker = MyStack();
}
// Handles the request of adding a element into stack
{
// add element in normal stack
this.stack.push(element);
// add element in tracker stack
if (this.tracker.isEmpty() == false && this.tracker.peek() > element)
{
this.tracker.push(this.tracker.peek());
}
else
{
this.tracker.push(element);
}
}
fun remove(): Unit
{
if (this.stack.isEmpty() == false)
{
print(" Pop Element : " + this.stack.peek() + "\n");
this.stack.pop();
}
if (this.tracker.isEmpty() == false)
{
this.tracker.pop();
}
}
fun maxElemenet(): Unit
{
if (this.stack.top != null && this.tracker.top != null)
{
// Display top element of current stack and max element in current instant
print(" Stack Top : " + this.stack.peek() + " Max is : " + this.tracker.peek() + " \n");
}
}
}
fun main(args: Array<String>): Unit
{
var obj: Tracking = Tracking();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
obj.remove();
obj.maxElemenet();
}``````

#### Output

`````` Stack Top : 8 Max is : 13
Pop Element : 8
Stack Top : 13 Max is : 13
Pop Element : 13
Stack Top : 3 Max is : 7``````

## Time Complexity

The time complexity of each operation in the `TrackerStack` is O(1) since it only involves pushing, popping, and peeking from the stacks, which takes constant time. Therefore, the overall time complexity for each operation in the `TrackerStack` is O(1).

The space complexity of the `TrackerStack` is O(N) due to the space used by the two separate stacks, where N is the number of elements in the stack.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post