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():

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 )
{

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 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();

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--;
}
}
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);
// 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();
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--;
}
}
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);
// 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();
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--;
}
}
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);
// 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();
/*
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--;
}
}
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 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();
/*
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--;
}
}
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 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();
/*
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

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 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()
#
#         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_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 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()
#
#         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;
}
}
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();
/*
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;
}
}
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 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();
/*
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;
}
}
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 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();
/*
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.

Categories
Relative Post