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():
        If the stack is not empty, return top.element

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)
{
	// Add stack 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++;
}
// return top element of stack
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();
	// Add the stack element
	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--;
		}
	}
	// return top element of stack
	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
	public void add(int element)
	{
		// 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();
		// Add the elements
		obj.add(6);
		obj.add(4);
		obj.add(7);
		obj.add(3);
		obj.add(13);
		obj.add(8);
		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--;
		}
	}
	// return top element of stack
	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
	void add(int element)
	{
		// 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();
	// Add the elements
	obj.add(6);
	obj.add(4);
	obj.add(7);
	obj.add(3);
	obj.add(13);
	obj.add(8);
	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--;
		}
	}
	// return top element of stack
	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
	public void add(int element)
	{
		// 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();
		// Add the elements
		obj.add(6);
		obj.add(4);
		obj.add(7);
		obj.add(3);
		obj.add(13);
		obj.add(8);
		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--;
		}
	}
	// return top element of stack
	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
	public	function add($element)
	{
		// 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();
	// Add the elements
	$obj->add(6);
	$obj->add(4);
	$obj->add(7);
	$obj->add(3);
	$obj->add(13);
	$obj->add(8);
	$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--;
		}
	}
	// return top element of stack
	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)
	{
		// 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();
	// Add the elements
	obj.add(6);
	obj.add(4);
	obj.add(7);
	obj.add(3);
	obj.add(13);
	obj.add(8);
	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
		
	
	#  return top element of stack
	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
	def add(self, element) :
		#  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()
	#  Add the elements
	obj.add(6)
	obj.add(4)
	obj.add(7)
	obj.add(3)
	obj.add(13)
	obj.add(8)
	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_reader :element, :next
	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_reader :top, :size
	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

	#  return top element of stack
	def peek() 
		return self.top.element
	end

end

class Tracking  
	# Define the accessor and reader of class Tracking  
	attr_reader :stack, :tracker
	attr_accessor :stack, :tracker
 
	
	def initialize() 
		self.stack = MyStack.new()
		self.tracker = MyStack.new()
	end

	#  Handles the request of adding a element into stack
	def add(element) 
		#  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()
	#  Add the elements
	obj.add(6)
	obj.add(4)
	obj.add(7)
	obj.add(3)
	obj.add(13)
	obj.add(8)
	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;
		}
	}
	// return top element of stack
	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();
		// Add the elements
		obj.add(6);
		obj.add(4);
		obj.add(7);
		obj.add(3);
		obj.add(13);
		obj.add(8);
		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;
		}
	}
	// return top element of stack
	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
	func add(_ element: Int)
	{
		// 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();
	// Add the elements
	obj.add(6);
	obj.add(4);
	obj.add(7);
	obj.add(3);
	obj.add(13);
	obj.add(8);
	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;
		}
	}
	// return top element of stack
	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
	fun 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);
		}
	}
	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();
	// Add the elements
	obj.add(6);
	obj.add(4);
	obj.add(7);
	obj.add(3);
	obj.add(13);
	obj.add(8);
	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.

New Comment