Posted on by Kalkicode
Code Stack

Tracking present minimum element in a stack

The problem of Tracking the present minimum element in a stack involves designing a stack data structure that keeps track of the minimum 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 minimum 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. minElement(): Get the minimum element present in the stack at any given time.

Example

Consider the following operations on the stack:

push(4)
push(7)
push(9)
push(2)
push(3)
push(8)
minElement() => Should return 2
pop()
minElement() => Should return 2
pop()
minElement() => Should return 2
pop()
minElement() => Should return 4

Idea to Solve the Problem

To track the minimum 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 minimum 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 smaller, 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 minimum 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 smaller, 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 minElement operation of TrackerStack, return the top element of the tracker stack, which represents the minimum 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 minElement():
        If the trackerStack is not empty, return trackerStack.peek()

Code Solution

// C program 
// Tracking the minimum 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 minElemenet(struct MyStack*stack)
{

    if(stack->top != NULL && tracker->top != NULL)
    {
        // Display top element of current stack and min element in current instant
        printf(" Stack Top : %d  min is : %d \n",stack->top->element , tracker->top->element);
    }
}


int main()
{
 

    tracker = newStack();

    struct MyStack * stack = newStack();

    // Add the stack element
    push(stack,4);
    push(stack,7);
    push(stack,9);
    push(stack,2);
    push(stack,3);
    push(stack,8);

    minElemenet(stack);


    pop(stack);

    minElemenet(stack);

    pop(stack);

    minElemenet(stack);

    pop(stack);

    minElemenet(stack);
    return 0;
}

Output

 Stack Top : 8  min is : 2
 Pop Element : 8
 Stack Top : 3  min is : 2
 Pop Element : 3
 Stack Top : 2  min is : 2
 Pop Element : 2
 Stack Top : 9  min is : 4
/*
    Java Program
    Tracking the minimum 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);
		// Add node 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)
		{
			System.out.print(" Pop Element : " + this.stack.peek() + "\n");
			this.stack.pop();
		}
		if (this.tracker.isEmpty() == false)
		{
			this.tracker.pop();
		}
	}
	public void minElemenet()
	{
		if (this.stack.top != null && this.tracker.top != null)
		{
			// Display top element of current stack and min element in current instant
			System.out.print(" Stack Top : " + this.stack.peek() + " min is : " + this.tracker.peek() + " \n");
		}
	}
	public static void main(String[] args)
	{
		Tracking obj = new Tracking();
		// Add the elements
		obj.add(4);
		obj.add(7);
		obj.add(9);
		obj.add(2);
		obj.add(3);
		obj.add(8);
		obj.minElemenet();
		obj.remove();
		obj.minElemenet();
		obj.remove();
		obj.minElemenet();
		obj.remove();
		obj.minElemenet();
	}
}

Output

 Stack Top : 8 min is : 2
 Pop Element : 8
 Stack Top : 3 min is : 2
 Pop Element : 3
 Stack Top : 2 min is : 2
 Pop Element : 2
 Stack Top : 9 min is : 4
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program
    Tracking the minimum 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
          	delete temp;
			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);
		// Add node in tracker stack
		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 minElemenet()
	{
		if (this->stack->top != NULL && this->tracker->top != NULL)
		{
			// Display top element of current stack and min element in current instant
			cout << " Stack Top : " << this->stack->peek() << " min is : " << this->tracker->peek() << " \n";
		}
	}
};
int main()
{
	Tracking obj = Tracking();
	// Add the elements
	obj.add(4);
	obj.add(7);
	obj.add(9);
	obj.add(2);
	obj.add(3);
	obj.add(8);
	obj.minElemenet();
	obj.remove();
	obj.minElemenet();
	obj.remove();
	obj.minElemenet();
	obj.remove();
	obj.minElemenet();
	return 0;
}

Output

 Stack Top : 8 min is : 2
 Pop Element : 8
 Stack Top : 3 min is : 2
 Pop Element : 3
 Stack Top : 2 min is : 2
 Pop Element : 2
 Stack Top : 9 min is : 4
// Include namespace system
using System;
/*
    C# Program
    Tracking the minimum 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 node in normal stack
        this.stack.push(element);
        // Add node 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 minElemenet()
    {
        if (this.stack.top != null && this.tracker.top != null)
        {
            // Display top element of current stack and min element in current instant
            Console.Write(" Stack Top : " + this.stack.peek() + " min is : " + this.tracker.peek() + " \n");
        }
    }
    public static void Main(String[] args)
    {
        Tracking obj = new Tracking();
        // Add the elements
        obj.add(4);
        obj.add(7);
        obj.add(9);
        obj.add(2);
        obj.add(3);
        obj.add(8);
        /*
        Stack Element
        -----------------
          top-> 8       2  <- Track Stack
                3       2
                2       2
                9       4
                7       4
                4       4    
        -------------------------
        */
        obj.minElemenet();
        obj.remove();
        obj.minElemenet();
        obj.remove();
        obj.minElemenet();
        obj.remove();
        obj.minElemenet();
    }
}

Output

 Stack Top : 8 min is : 2
 Pop Element : 8
 Stack Top : 3 min is : 2
 Pop Element : 3
 Stack Top : 2 min is : 2
 Pop Element : 2
 Stack Top : 9 min is : 4
<?php
/*
    Php Program
    Tracking the minimum 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 node in normal stack
        $this->stack->push($element);
        // Add node 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 minElemenet()
    {
        if ($this->stack->top != null && $this->tracker->top != null)
        {
            // Display top element of current stack and min element in current instant
            echo " Stack Top : ". $this->stack->peek() ." min is : ". $this->tracker->peek() ." \n";
        }
    }
}

function main()
{
    $obj = new Tracking();
    // Add the elements
    $obj->add(4);
    $obj->add(7);
    $obj->add(9);
    $obj->add(2);
    $obj->add(3);
    $obj->add(8);
    /*
    Stack Element
    -----------------
      top-> 8       2  <- Track Stack
            3       2
            2       2
            9       4
            7       4
            4       4    
    -------------------------
    */
    $obj->minElemenet();
    $obj->remove();
    $obj->minElemenet();
    $obj->remove();
    $obj->minElemenet();
    $obj->remove();
    $obj->minElemenet();
}
main();

Output

 Stack Top : 8 min is : 2
 Pop Element : 8
 Stack Top : 3 min is : 2
 Pop Element : 3
 Stack Top : 2 min is : 2
 Pop Element : 2
 Stack Top : 9 min is : 4
/*
    Node Js Program
    Tracking the minimum 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 node in normal stack
        this.stack.push(element);
        // Add node 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();
        }
    }
    minElemenet()
    {
        if (this.stack.top != null && this.tracker.top != null)
        {
            // Display top element of current stack and min element in current instant
            process.stdout.write(" Stack Top : " + this.stack.peek() + " min is : " + this.tracker.peek() + " \n");
        }
    }
}

function main()
{
    var obj = new Tracking();
    // Add the elements
    obj.add(4);
    obj.add(7);
    obj.add(9);
    obj.add(2);
    obj.add(3);
    obj.add(8);
    /*
    Stack Element
    -----------------
      top-> 8       2  <- Track Stack
            3       2
            2       2
            9       4
            7       4
            4       4    
    -------------------------
    */
    obj.minElemenet();
    obj.remove();
    obj.minElemenet();
    obj.remove();
    obj.minElemenet();
    obj.remove();
    obj.minElemenet();
}
main();

Output

 Stack Top : 8 min is : 2
 Pop Element : 8
 Stack Top : 3 min is : 2
 Pop Element : 3
 Stack Top : 2 min is : 2
 Pop Element : 2
 Stack Top : 9 min is : 4
#  Python 3 Program
#  Tracking the minimum 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 node in normal stack
		self.stack.push(element)
		#  Add node 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 minElemenet(self) :
		if (self.stack.top != None and self.tracker.top != None) :
			#  Display top element of current stack and min element in current instant
			print(" Stack Top : ", self.stack.peek() ," min is : ", self.tracker.peek() ," ")
		
	

def main() :
	obj = Tracking()
	#  Add the elements
	obj.add(4)
	obj.add(7)
	obj.add(9)
	obj.add(2)
	obj.add(3)
	obj.add(8)
	# 
	#         Stack Element
	#         -----------------
	#           top-> 8       2  <- Track Stack
	#                 3       2
	#                 2       2
	#                 9       4
	#                 7       4
	#                 4       4    
	#         -------------------------
	#         
	
	obj.minElemenet()
	obj.remove()
	obj.minElemenet()
	obj.remove()
	obj.minElemenet()
	obj.remove()
	obj.minElemenet()

if __name__ == "__main__": main()

Output

 Stack Top :  8  min is :  2
 Pop Element :  8
 Stack Top :  3  min is :  2
 Pop Element :  3
 Stack Top :  2  min is :  2
 Pop Element :  2
 Stack Top :  9  min is :  4
#  Ruby Program
#  Tracking the minimum 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 node in normal stack
		self.stack.push(element)
		#  Add node 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 minElemenet() 
		if (self.stack.top != nil && self.tracker.top != nil) 
			#  Display top element of current stack and min element in current instant
			print(" Stack Top : ", self.stack.peek() ," min is : ", self.tracker.peek() ," \n")
		end

	end

end

def main() 
	obj = Tracking.new()
	#  Add the elements
	obj.add(4)
	obj.add(7)
	obj.add(9)
	obj.add(2)
	obj.add(3)
	obj.add(8)
	# 
	#         Stack Element
	#         -----------------
	#         top-> 8       2  <- Track Stack
	#                 3       2
	#                 2       2
	#                 9       4
	#                 7       4
	#                 4       4    
	#         -------------------------
	#         
	
	obj.minElemenet()
	obj.remove()
	obj.minElemenet()
	obj.remove()
	obj.minElemenet()
	obj.remove()
	obj.minElemenet()
end

main()

Output

 Stack Top : 8 min is : 2 
 Pop Element : 8
 Stack Top : 3 min is : 2 
 Pop Element : 3
 Stack Top : 2 min is : 2 
 Pop Element : 2
 Stack Top : 9 min is : 4 
/*
    Scala Program
    Tracking the minimum 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 node in normal stack
        this.stack.push(element);
        // Add node 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 minElemenet(): Unit = {
        if (this.stack.top != null && this.tracker.top != null)
        {
            // Display top element of current stack and min element in current instant
            print(" Stack Top : " + this.stack.peek() + " min is : " + this.tracker.peek() + " \n");
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var obj: Tracking = new Tracking();
        // Add the elements
        obj.add(4);
        obj.add(7);
        obj.add(9);
        obj.add(2);
        obj.add(3);
        obj.add(8);
        /*
        Stack Element
        -----------------
          top-> 8       2  <- Track Stack
                3       2
                2       2
                9       4
                7       4
                4       4    
        -------------------------
        */
        obj.minElemenet();
        obj.remove();
        obj.minElemenet();
        obj.remove();
        obj.minElemenet();
        obj.remove();
        obj.minElemenet();
    }
}

Output

 Stack Top : 8 min is : 2
 Pop Element : 8
 Stack Top : 3 min is : 2
 Pop Element : 3
 Stack Top : 2 min is : 2
 Pop Element : 2
 Stack Top : 9 min is : 4
/*
    Swift 4 Program
    Tracking the minimum 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 node in normal stack
		self.stack!.push(element);
		// Add node 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 minElemenet()
	{
		if (self.stack!.top != nil && self.tracker!.top != nil)
		{
			// Display top element of current stack and min element in current instant
			print(" Stack Top : ", self.stack!.peek() ," min is : ", self.tracker!.peek() ," ");
		}
	}
}
func main()
{
	let obj: Tracking = Tracking();
	// Add the elements
	obj.add(4);
	obj.add(7);
	obj.add(9);
	obj.add(2);
	obj.add(3);
	obj.add(8);
	/*
	        Stack Element
	        -----------------
	        top-> 8       2  <- Track Stack
	                3       2
	                2       2
	                9       4
	                7       4
	                4       4    
	        -------------------------
	        */
	obj.minElemenet();
	obj.remove();
	obj.minElemenet();
	obj.remove();
	obj.minElemenet();
	obj.remove();
	obj.minElemenet();
}
main();

Output

 Stack Top :  8  min is :  2
 Pop Element :  8
 Stack Top :  3  min is :  2
 Pop Element :  3
 Stack Top :  2  min is :  2
 Pop Element :  2
 Stack Top :  9  min is :  4
/*
    Kotlin Program
    Tracking the minimum 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 node in normal stack
        this.stack.push(element);
        // Add node 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 minElemenet(): Unit
    {
        if (this.stack.top != null && this.tracker.top != null)
        {
            // Display top element of current stack and min element in current instant
            print(" Stack Top : " + this.stack.peek() + " min is : " + this.tracker.peek() + " \n");
        }
    }
}
fun main(args: Array<String>): Unit
{
    var obj: Tracking = Tracking();
    // Add the elements
    obj.add(4);
    obj.add(7);
    obj.add(9);
    obj.add(2);
    obj.add(3);
    obj.add(8);
    /*
    Stack Element
    -----------------
      top-> 8       2  <- Track Stack
            3       2
            2       2
            9       4
            7       4
            4       4    
    -------------------------
    */
    obj.minElemenet();
    obj.remove();
    obj.minElemenet();
    obj.remove();
    obj.minElemenet();
    obj.remove();
    obj.minElemenet();
}

Output

 Stack Top : 8 min is : 2
 Pop Element : 8
 Stack Top : 3 min is : 2
 Pop Element : 3
 Stack Top : 2 min is : 2
 Pop Element : 2
 Stack Top : 9 min is : 4

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