Posted on by Kalkicode
Code Recursion

# Sort a stack using recursion

A stack is a linear data structure that follows the Last In First Out (LIFO) principle, where the element added last is the one that will be removed first. The task is to sort the elements within the stack in ascending order using recursion.

## Problem Statement

Given a stack of integers, the goal is to sort the elements in ascending order using a recursive approach.

## Example

Given a stack with the following elements: [6, 5, 8, 3, 2, 9, 7, 4], the output of the program should display the sorted stack: [2, 3, 4, 5, 6, 7, 8, 9].

## Solution Idea

The solution involves using recursion to sort the stack in ascending order. The basic idea is to pop the top element from the stack, recursively sort the remaining elements, and then insert the popped element at its correct position in the sorted sub-stack.

## Pseudocode

``````sortedAdd(stack, element):
if stack is empty or top of stack > element:
push element into stack
else:
data = top element of stack
pop element from stack
push data back into stack

sortStack(stack):
if stack is not empty:
element = top element of stack
pop element from stack
sortStack(stack)

## Algorithm Explanation

1. The `sortedAdd` function adds an element to the stack in its sorted position. If the stack is empty or the top element is greater than the new element, the new element is pushed onto the stack. Otherwise, the top element is temporarily removed, the new element is added using a recursive call, and then the removed element is added back to the stack.
2. The `sortStack` function sorts the stack using a recursive approach. It pops the top element, recursively sorts the remaining elements, and then uses the `sortedAdd` function to insert the popped element at its appropriate position in the sorted sub-stack.

## Code Solution

``````// C program
// Sort a stack using recursion
#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 *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;
}
// Returns the status of empty or non empty stacks
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);
stack->size++;
}
int peek(struct MyStack *stack)
{
return stack->top->element;
}
// 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;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}
void sortedAdd(struct MyStack *stack, int element)
{
if (isEmpty(stack) == 1 || peek(stack) > element)
{
// When stack is empty,  Or top of stack is higher of equal to new insert element
push(stack, element);
}
else
{
// Get top element
int data = peek(stack);
// Remove top element
pop(stack);
push(stack, data);
}
}
void sortStack(struct MyStack *stack)
{
if (isEmpty(stack) == 0)
{
//When stack not empty
// Get top element
int element = peek(stack);
// Remove top element
pop(stack);
sortStack(stack);
// Add element in sorted way
}
}
// Print element of stack
void printData(struct MyStack *stack)
{
struct StackNode *temp = stack->top;
while (temp != NULL)
{
// Display element value
printf("  %d", temp->element);
temp = temp->next;
}
printf("\n");
}
int main()
{
struct MyStack *stack = newStack();
push(stack, 4);
push(stack, 7);
push(stack, 9);
push(stack, 2);
push(stack, 3);
push(stack, 8);
push(stack, 5);
push(stack, 6);
/*
Created Stack
============

6 <- Top
5
8
3
2
9
7
4

*/
printf("\n Before Sort \n");
printData(stack);
// Sort operation
sortStack(stack);
/*
Sort Stack
============
2   <- Top
3
4
5
6
7
8
9
*/
printf("\n After Sort \n");
printData(stack);
return 0;
}``````

#### Output

`````` Before Sort
6  5  8  3  2  9  7  4

After Sort
2  3  4  5  6  7  8  9``````
``````/*
Java Program
Sort a stack using recursion
*/
// 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 SortStackElement
{
public MyStack stack;
public SortStackElement()
{
this.stack = new MyStack();
}
// Print element of stack
public void printData()
{
StackNode temp = this.stack.top;
while (temp != null)
{
// Display element value
System.out.print("   " + temp.element);
temp = temp.next;
}
System.out.print("\n");
}
// Add element in sorted position
{
if (this.stack.isEmpty() == true || this.stack.peek() > element)
{
// When stack is empty,  Or top of stack is higher of equal to new insert element
this.stack.push(element);
}
else
{
// Get top element
int data = this.stack.peek();
// Remove top element
this.stack.pop();
this.stack.push(data);
}
}
// Split element of stack and combine in sorted order
public void sortStack()
{
if (this.stack.isEmpty() == false)
{
//When stack not empty
// Get top element
int element = this.stack.peek();
// Remove top element
this.stack.pop();
this.sortStack();
// Add element in sorted way
}
}
public static void main(String[] args)
{
/*
Created Stack
============

6 <- Top
5
8
3
2
9
7
4

*/
System.out.print("\n Before Sort \n");
// Sort operation
/*
Sort Stack
============
2   <- Top
3
4
5
6
7
8
9
*/
System.out.print("\n After Sort \n");
}
}``````

#### Output

`````` Before Sort
6   5   8   3   2   9   7   4

After Sort
2   3   4   5   6   7   8   9``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Sort a stack using recursion
*/
// Define stack node
class StackNode
{
public: int element;
StackNode *next;
StackNode(int element, StackNode *next)
{
this->element = element;
this->next = next;
}
};
// Define a custom stack
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
temp = NULL;
this->size--;
}
}
int peek()
{
return this->top->element;
}
};
class SortStackElement
{
public:
MyStack *stack;
SortStackElement()
{
this->stack = new MyStack();
}
// Print element of stack
void printData()
{
StackNode *temp = this->stack->top;
while (temp != NULL)
{
// Display element value
cout << "   " << temp->element;
temp = temp->next;
}
cout << "\n";
}
// Add element in sorted position
{
if (this->stack->isEmpty() == true || this->stack->peek() > element)
{
// When stack is empty,  Or top of stack is higher of equal to new insert element
this->stack->push(element);
}
else
{
// Get top element
int data = this->stack->peek();
// Remove top element
this->stack->pop();
this->stack->push(data);
}
}
// Split element of stack and combine in sorted order
void sortStack()
{
if (this->stack->isEmpty() == false)
{
//When stack not empty
// Get top element
int element = this->stack->peek();
// Remove top element
this->stack->pop();
this->sortStack();
// Add element in sorted way
}
}
};
int main()
{
/*
Created Stack
============

6 <- Top
5
8
3
2
9
7
4

*/
cout << "\n Before Sort \n";
// Sort operation
/*
Sort Stack
============
2   <- Top
3
4
5
6
7
8
9
*/

cout << "\n After Sort \n";
return 0;
}``````

#### Output

`````` Before Sort
6   5   8   3   2   9   7   4

After Sort
2   3   4   5   6   7   8   9``````
``````// Include namespace system
using System;
/*
C# Program
Sort a stack using recursion
*/
// 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 SortStackElement
{
public MyStack stack;
public SortStackElement()
{
this.stack = new MyStack();
}
// Print element of stack
public void printData()
{
StackNode temp = this.stack.top;
while (temp != null)
{
// Display element value
Console.Write("   " + temp.element);
temp = temp.next;
}
Console.Write("\n");
}
// Add element in sorted position
{
if (this.stack.isEmpty() == true || this.stack.peek() > element)
{
// When stack is empty,  Or top of stack is higher of equal to new insert element
this.stack.push(element);
}
else
{
// Get top element
int data = this.stack.peek();
// Remove top element
this.stack.pop();
this.stack.push(data);
}
}
// Split element of stack and combine in sorted order
public void sortStack()
{
if (this.stack.isEmpty() == false)
{
//When stack not empty
// Get top element
int element = this.stack.peek();
// Remove top element
this.stack.pop();
this.sortStack();
// Add element in sorted way
}
}
public static void Main(String[] args)
{
/*
Created Stack
============

6 <- Top
5
8
3
2
9
7
4

*/
Console.Write("\n Before Sort \n");
// Sort operation
/*
Sort Stack
============
2   <- Top
3
4
5
6
7
8
9
*/
Console.Write("\n After Sort \n");
}
}``````

#### Output

`````` Before Sort
6   5   8   3   2   9   7   4

After Sort
2   3   4   5   6   7   8   9``````
``````<?php
/*
Php Program
Sort a stack using recursion
*/
// 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 SortStackElement
{
public \$stack;

function __construct()
{
\$this->stack = new MyStack();
}
// Print element of stack
public	function printData()
{
\$temp = \$this->stack->top;
while (\$temp != null)
{
// Display element value
echo "   ". \$temp->element;
\$temp = \$temp->next;
}
echo "\n";
}
// Add element in sorted position
{
if (\$this->stack->isEmpty() == true || \$this->stack->peek() > \$element)
{
// When stack is empty,  Or top of stack is higher of equal to new insert element
\$this->stack->push(\$element);
}
else
{
// Get top element
\$data = \$this->stack->peek();
// Remove top element
\$this->stack->pop();
\$this->stack->push(\$data);
}
}
// Split element of stack and combine in sorted order
public	function sortStack()
{
if (\$this->stack->isEmpty() == false)
{
//When stack not empty
// Get top element
\$element = \$this->stack->peek();
// Remove top element
\$this->stack->pop();
\$this->sortStack();
// Add element in sorted way
}
}
}

function main()
{
/*
Created Stack
============

6 <- Top
5
8
3
2
9
7
4

*/
echo "\n Before Sort \n";
// Sort operation
/*
Sort Stack
============
2   <- Top
3
4
5
6
7
8
9
*/
echo "\n After Sort \n";
}
main();``````

#### Output

`````` Before Sort
6   5   8   3   2   9   7   4

After Sort
2   3   4   5   6   7   8   9``````
``````/*
Node Js Program
Sort a stack using recursion
*/
// 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 SortStackElement
{
constructor()
{
this.stack = new MyStack();
}
// Print element of stack
printData()
{
var temp = this.stack.top;
while (temp != null)
{
// Display element value
process.stdout.write("   " + temp.element);
temp = temp.next;
}
process.stdout.write("\n");
}
// Add element in sorted position
{
if (this.stack.isEmpty() == true || this.stack.peek() > element)
{
// When stack is empty,  Or top of stack is higher of equal to new insert element
this.stack.push(element);
}
else
{
// Get top element
var data = this.stack.peek();
// Remove top element
this.stack.pop();
this.stack.push(data);
}
}
// Split element of stack and combine in sorted order
sortStack()
{
if (this.stack.isEmpty() == false)
{
//When stack not empty
// Get top element
var element = this.stack.peek();
// Remove top element
this.stack.pop();
this.sortStack();
// Add element in sorted way
}
}
}

function main()
{
/*
Created Stack
============

6 <- Top
5
8
3
2
9
7
4

*/
process.stdout.write("\n Before Sort \n");
// Sort operation
/*
Sort Stack
============
2   <- Top
3
4
5
6
7
8
9
*/
process.stdout.write("\n After Sort \n");
}
main();``````

#### Output

`````` Before Sort
6   5   8   3   2   9   7   4

After Sort
2   3   4   5   6   7   8   9``````
``````#  Python 3 Program
#  Sort a stack using recursion

#  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 SortStackElement :

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

#  Print element of stack
def printData(self) :
temp = self.stack.top
while (temp != None) :
#  Display element value
print("   ", temp.element, end = "")
temp = temp.next

print(end = "\n")

#  Add element in sorted position
if (self.stack.isEmpty() == True or self.stack.peek() > element) :
#  When stack is empty,  Or top of stack is higher of equal to new insert element
self.stack.push(element)
else :
#  Get top element
data = self.stack.peek()
#  Remove top element
self.stack.pop()
self.stack.push(data)

#  Split element of stack and combine in sorted order
def sortStack(self) :
if (self.stack.isEmpty() == False) :
# When stack not empty
#  Get top element
element = self.stack.peek()
#  Remove top element
self.stack.pop()
self.sortStack()
#  Add element in sorted way

def main() :
#
# 		Created Stack
# 		============
# 		    6 <- Top
# 		    5
# 		    8
# 		    3
# 		    2
# 		    9
# 		    7
# 		    4
#

print("\n Before Sort ")
#  Sort operation
#
# 		Sort Stack
# 		============
# 		    2   <- Top
# 		    3
# 		    4
# 		    5
# 		    6
# 		    7
# 		    8
# 		    9
#

print("\n After Sort ")

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

#### Output

`````` Before Sort
6    5    8    3    2    9    7    4

After Sort
2    3    4    5    6    7    8    9``````
``````#  Ruby Program
#  Sort a stack using recursion

#  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 SortStackElement
# Define the accessor and reader of class SortStackElement
attr_accessor :stack

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

#  Print element of stack
def printData()
temp = self.stack.top
while (temp != nil)
#  Display element value
print("   ", temp.element)
temp = temp.next
end

print("\n")
end

#  Add element in sorted position
if (self.stack.isEmpty() == true || self.stack.peek() > element)
#  When stack is empty,  Or top of stack is higher of equal to new insert element
self.stack.push(element)
else
#  Get top element
data = self.stack.peek()
#  Remove top element
self.stack.pop()
self.stack.push(data)
end

end

#  Split element of stack and combine in sorted order
def sortStack()
if (self.stack.isEmpty() == false)
# When stack not empty
#  Get top element
element = self.stack.peek()
#  Remove top element
self.stack.pop()
self.sortStack()
#  Add element in sorted way
end

end

end

def main()
#
# 		Created Stack
# 		============
# 		    6 <- Top
# 		    5
# 		    8
# 		    3
# 		    2
# 		    9
# 		    7
# 		    4
#

print("\n Before Sort \n")
#  Sort operation
#
# 		Sort Stack
# 		============
# 		    2   <- Top
# 		    3
# 		    4
# 		    5
# 		    6
# 		    7
# 		    8
# 		    9
#

print("\n After Sort \n")
end

main()``````

#### Output

`````` Before Sort
6   5   8   3   2   9   7   4

After Sort
2   3   4   5   6   7   8   9
``````
``````/*
Scala Program
Sort a stack using recursion
*/
// 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 SortStackElement(var stack: MyStack)
{
def this()
{
this(new MyStack());
}
// Print element of stack
def printData(): Unit = {
var temp: StackNode = this.stack.top;
while (temp != null)
{
// Display element value
print("   " + temp.element);
temp = temp.next;
}
print("\n");
}
// Add element in sorted position
def sortedAdd(element: Int): Unit = {
if (this.stack.isEmpty() == true || this.stack.peek() > element)
{
// When stack is empty,  Or top of stack is higher of equal to new insert element
this.stack.push(element);
}
else
{
// Get top element
var data: Int = this.stack.peek();
// Remove top element
this.stack.pop();
this.stack.push(data);
}
}
// Split element of stack and combine in sorted order
def sortStack(): Unit = {
if (this.stack.isEmpty() == false)
{
//When stack not empty
// Get top element
var element: Int = this.stack.peek();
// Remove top element
this.stack.pop();
this.sortStack();
// Add element in sorted way
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SortStackElement = new SortStackElement();
/*
Created Stack
============

6 <- Top
5
8
3
2
9
7
4

*/
print("\n Before Sort \n");
// Sort operation
/*
Sort Stack
============
2   <- Top
3
4
5
6
7
8
9
*/
print("\n After Sort \n");
}
}``````

#### Output

`````` Before Sort
6   5   8   3   2   9   7   4

After Sort
2   3   4   5   6   7   8   9``````
``````/*
Swift 4 Program
Sort a stack using recursion
*/
// 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 SortStackElement
{
var stack: MyStack? ;
init()
{
self.stack = MyStack();
}
// Print element of stack
func printData()
{
var temp: StackNode? = self.stack!.top;
while (temp != nil)
{
// Display element value
print("   ", temp!.element, terminator: "");
temp = temp!.next;
}
print(terminator: "\n");
}
// Add element in sorted position
{
if (self.stack!.isEmpty() == true || self.stack!.peek() > element)
{
// When stack is empty,  Or top of stack is higher of equal to new insert element
self.stack!.push(element);
}
else
{
// Get top element
let data: Int = self.stack!.peek();
// Remove top element
self.stack!.pop();
self.stack!.push(data);
}
}
// Split element of stack and combine in sorted order
func sortStack()
{
if (self.stack!.isEmpty() == false)
{
//When stack not empty
// Get top element
let element: Int = self.stack!.peek();
// Remove top element
self.stack!.pop();
self.sortStack();
// Add element in sorted way
}
}
}
func main()
{
/*
Created Stack
============

6 <- Top
5
8
3
2
9
7
4

*/
print("\n Before Sort ");
// Sort operation
/*
Sort Stack
============
2   <- Top
3
4
5
6
7
8
9
*/
print("\n After Sort ");
}
main();``````

#### Output

`````` Before Sort
6    5    8    3    2    9    7    4

After Sort
2    3    4    5    6    7    8    9``````
``````/*
Kotlin Program
Sort a stack using recursion
*/
// 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 SortStackElement
{
var stack: MyStack;
constructor()
{
this.stack = MyStack();
}
// Print element of stack
fun printData(): Unit
{
var temp: StackNode ? = this.stack.top;
while (temp != null)
{
// Display element value
print("   " + temp.element);
temp = temp.next;
}
print("\n");
}
// Add element in sorted position
{
if (this.stack.isEmpty() == true || this.stack.peek()>element)
{
// When stack is empty,  Or top of stack is higher of equal to new insert element
this.stack.push(element);
}
else
{
// Get top element
var data: Int = this.stack.peek();
// Remove top element
this.stack.pop();
this.stack.push(data);
}
}
// Split element of stack and combine in sorted order
fun sortStack(): Unit
{
if (this.stack.isEmpty() == false)
{
//When stack not empty
// Get top element
var element: Int = this.stack.peek();
// Remove top element
this.stack.pop();
this.sortStack();
// Add element in sorted way
}
}
}
fun main(args: Array<String>): Unit
{
/*
Created Stack
============

6 <- Top
5
8
3
2
9
7
4

*/
print("\n Before Sort \n");
// Sort operation
/*
Sort Stack
============
2   <- Top
3
4
5
6
7
8
9
*/
print("\n After Sort \n");
}``````

#### Output

`````` Before Sort
6   5   8   3   2   9   7   4

After Sort
2   3   4   5   6   7   8   9``````

## Output Explanation

The output first displays the original unsorted stack: [6, 5, 8, 3, 2, 9, 7, 4]. After calling the `sortStack` function, the sorted stack is displayed: [2, 3, 4, 5, 6, 7, 8, 9].

## Time Complexity

The time complexity of the algorithm depends on the recursive operations. In the worst case, the algorithm performs O(N^2) operations, where N is the number of elements in the stack. This is because for each element, the stack is traversed to insert the element in sorted order.

## 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