Posted on by Kalkicode
Code Stack

# Sort a stack using temporary two stack

The problem is to sort a stack using temporary two auxiliary stacks. The goal is to implement a sorting algorithm that takes an input stack and rearranges its elements in ascending order using two additional temporary stacks.

## Problem Statement

Given a stack, we need to sort its elements in ascending order using two temporary auxiliary stacks.

## Explanation with Suitable Example

Let's consider the following stack:

``````8
7
6
5
4
3
2
1
``````

The goal is to sort this stack in ascending order:

``````1
2
3
4
5
6
7
8
``````

## Idea to Solve the Problem

The main idea behind sorting the stack using two auxiliary stacks is to simulate the process of selection sort. We use two temporary stacks to help rearrange the elements in ascending order.

1. We create two auxiliary stacks, say `auxiliary1` and `auxiliary2`.
2. We transfer all the elements from the original stack to `auxiliary1`.
3. We find the minimum element in `auxiliary1`, pop it, and push it into `auxiliary2`.
4. We repeat this process until `auxiliary1` is empty.
5. The elements in `auxiliary2` are now in ascending order.
6. We transfer all the elements from `auxiliary2` back to the original stack.

## Pseudocode

The following pseudocode outlines the steps to sort a stack using two auxiliary stacks:

``````function transferData(t1, t2)
while t1 is not empty
data = top of t1
pop top of t1
push data into t2

function reverseStack(stack)
create auxiliary1 and auxiliary2 as empty stacks
transfer all elements from stack to auxiliary1
while auxiliary1 is not empty
find the minimum element in auxiliary1
pop it from auxiliary1 and push it into auxiliary2
transfer all elements from auxiliary2 back to stack

``````

## Algorithm Explanation

1. The `transferData` function takes two stacks `t1` and `t2` as input and transfers all the elements from `t1` to `t2` in their original order.
2. The `reverseStack` function creates two auxiliary stacks, `auxiliary1` and `auxiliary2`.
3. It transfers all the elements from the original stack to `auxiliary1` using the `transferData` function.
4. While `auxiliary1` is not empty, it finds the minimum element in `auxiliary1`, pops it from `auxiliary1`, and pushes it into `auxiliary2`.
5. This process is repeated until `auxiliary1` becomes empty, and `auxiliary2` now contains the elements of the original stack in ascending order.
6. Finally, the `transferData` function is used again to transfer all the elements from `auxiliary2` back to the original stack, resulting in a sorted stack.
``````// C program
// Sort a stack using temporary two stack
// Time complexity O(n)
#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--;
}
}
// Print element of stack
void printData(struct MyStack *stack)
{
struct StackNode *temp = stack->top;
// iterate stack elements
while (temp != NULL)
{
// Display element value
printf("  %d", temp->element);
temp = temp->next;
}
printf("\n");
}
// Transfer all stack t1 data into a stack t2
void transferData(struct MyStack *t1, struct MyStack *t2)
{
int data = 0;
// Executing the loop until when t1 stack element are not empty
while (isEmpty(t1) == 0)
{
// Get the top element of t1 stack
data = peek(t1);
// Remove top of current t1 stack
pop(t1);
// Add data to t2 stack
push(t2, data);
}
}
// This is reverse the stack elements by using of auxiliary stacks
void reverseStack(struct MyStack *stack)
{
// Create two auxiliary stacks
struct MyStack *auxiliary1 = newStack();
struct MyStack *auxiliary2 = newStack();
// Send the all elements from actual stack into auxiliary1
transferData(stack, auxiliary1);
// Send the all elements from auxiliary1 into auxiliary2
transferData(auxiliary1, auxiliary2);
// Send the all elements from auxiliary2 into actual stack
transferData(auxiliary2, stack);
}
int main()
{
// Create a stack
struct MyStack *stack = newStack();
push(stack, 1);
push(stack, 2);
push(stack, 3);
push(stack, 4);
push(stack, 5);
push(stack, 6);
push(stack, 7);
push(stack, 8);

/*
Constructed stack
==========
8  <-- Top
7
6
5
4
3
2
1
*/
// Display stack elements
printf(" Before Reverse \n");
printData(stack);
// Perform reverse operation
reverseStack(stack);

/*
After reverse
==========
1  <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
printf("\n After Reverse \n");
printData(stack);
return 0;
}``````

#### Output

`````` Before Reverse
8  7  6  5  4  3  2  1

After Reverse
1  2  3  4  5  6  7  8``````
``````/*
Java Program
The Stock Span Problem
*/
// 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 ReverseElements
{
// Print element of stack
public void printData(MyStack stack)
{
StackNode temp = stack.top;
// iterate stack elements
while (temp != null)
{
// Display element value
System.out.print("  " + temp.element);
temp = temp.next;
}
System.out.print("\n");
}
// Transfer all stack t1 data into a stack t2
public void transferData(MyStack t1, MyStack t2)
{
int data = 0;
// Executing the loop until when t1 stack element are not empty
while (t1.isEmpty() == false)
{
// Get the top element of t1 stack
data = t1.peek();
// Remove top of current t1 stack
t1.pop();
// Add data to t2 stack
t2.push(data);
}
}
// This is reverse the stack elements by using of auxiliary stacks
public void reverseStack(MyStack stack)
{
// Create two auxiliary stacks
MyStack auxiliary1 = new MyStack();
MyStack auxiliary2 = new MyStack();
// Send the all elements from actual stack into auxiliary1
transferData(stack, auxiliary1);
// Send the all elements from auxiliary1 into auxiliary2
transferData(auxiliary1, auxiliary2);
// Send the all elements from auxiliary2 into actual stack
transferData(auxiliary2, stack);
}
public static void main(String[] args)
{
// Create a stack
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
/*
Constructed stack
==========
8  <-- Top
7
6
5
4
3
2
1
*/
// Display stack elements
System.out.print(" Before Reverse \n");
// Perform reverse operation
/*
After reverse
==========
1  <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
System.out.print("\n After Reverse \n");
}
}``````

#### Output

`````` Before Reverse
8  7  6  5  4  3  2  1

After Reverse
1  2  3  4  5  6  7  8``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
The Stock Span Problem
*/
// 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 ReverseElements
{
public:
// Print element of stack
void printData(MyStack stack)
{
StackNode *temp = stack.top;
// iterate stack elements
while (temp != NULL)
{
// Display element value
cout << "  " << temp->element;
temp = temp->next;
}
cout << "\n";
}
// Transfer all stack t1 data into a stack t2
void transferData(MyStack &t1, MyStack &t2)
{
int data = 0;
// Executing the loop until when t1 stack element are not empty
while (t1.isEmpty() == false)
{
// Get the top element of t1 stack
data = t1.peek();
// Remove top of current t1 stack
t1.pop();
// Add data to t2 stack
t2.push(data);
}
}
// This is reverse the stack elements by using of auxiliary stacks
void reverseStack(MyStack &stack)
{
// Create two auxiliary stacks
MyStack auxiliary1 =  MyStack();
MyStack auxiliary2 =  MyStack();
// Send the all elements from actual stack into auxiliary1
this->transferData(stack, auxiliary1);
// Send the all elements from auxiliary1 into auxiliary2
this->transferData(auxiliary1, auxiliary2);
// Send the all elements from auxiliary2 into actual stack
this->transferData(auxiliary2, stack);

}
};
int main()
{
// Create a stack
MyStack stack = MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
/*
Constructed stack
==========
8  <-- Top
7
6
5
4
3
2
1
*/
// Display stack elements
cout << " Before Reverse \n";
// Perform reverse operation
/*
After reverse
==========
1  <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
cout << "\n After Reverse \n";
return 0;
}``````

#### Output

`````` Before Reverse
8  7  6  5  4  3  2  1

After Reverse
1  2  3  4  5  6  7  8``````
``````// Include namespace system
using System;
/*
C# Program
The Stock Span Problem
*/
// 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 ReverseElements
{
// Print element of stack
public void printData(MyStack stack)
{
StackNode temp = stack.top;
// iterate stack elements
while (temp != null)
{
// Display element value
Console.Write("  " + temp.element);
temp = temp.next;
}
Console.Write("\n");
}
// Transfer all stack t1 data into a stack t2
public void transferData(MyStack t1, MyStack t2)
{
int data = 0;
// Executing the loop until when t1 stack element are not empty
while (t1.isEmpty() == false)
{
// Get the top element of t1 stack
data = t1.peek();
// Remove top of current t1 stack
t1.pop();
// Add data to t2 stack
t2.push(data);
}
}
// This is reverse the stack elements by using of auxiliary stacks
public void reverseStack(MyStack stack)
{
// Create two auxiliary stacks
MyStack auxiliary1 = new MyStack();
MyStack auxiliary2 = new MyStack();
// Send the all elements from actual stack into auxiliary1
transferData(stack, auxiliary1);
// Send the all elements from auxiliary1 into auxiliary2
transferData(auxiliary1, auxiliary2);
// Send the all elements from auxiliary2 into actual stack
transferData(auxiliary2, stack);
}
public static void Main(String[] args)
{
// Create a stack
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
/*
Constructed stack
==========
8  <-- Top
7
6
5
4
3
2
1
*/
// Display stack elements
Console.Write(" Before Reverse \n");
// Perform reverse operation
/*
After reverse
==========
1  <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
Console.Write("\n After Reverse \n");
}
}``````

#### Output

`````` Before Reverse
8  7  6  5  4  3  2  1

After Reverse
1  2  3  4  5  6  7  8``````
``````<?php
/*
Php Program
The Stock Span Problem
*/
// 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 ReverseElements
{
// Print element of stack
public  function printData(\$stack)
{
\$temp = \$stack->top;
// iterate stack elements
while (\$temp != null)
{
// Display element value
echo "  ". \$temp->element;
\$temp = \$temp->next;
}
echo "\n";
}
// Transfer all stack t1 data into a stack t2
public  function transferData(\$t1, \$t2)
{
\$data = 0;
// Executing the loop until when t1 stack element are not empty
while (\$t1->isEmpty() == false)
{
// Get the top element of t1 stack
\$data = \$t1->peek();
// Remove top of current t1 stack
\$t1->pop();
// Add data to t2 stack
\$t2->push(\$data);
}
}
// This is reverse the stack elements by using of auxiliary stacks
public  function reverseStack(\$stack)
{
// Create two auxiliary stacks
\$auxiliary1 = new MyStack();
\$auxiliary2 = new MyStack();
// Send the all elements from actual stack into auxiliary1
\$this->transferData(\$stack, \$auxiliary1);
// Send the all elements from auxiliary1 into auxiliary2
\$this->transferData(\$auxiliary1, \$auxiliary2);
// Send the all elements from auxiliary2 into actual stack
\$this->transferData(\$auxiliary2, \$stack);
}
}

function main()
{
// Create a stack
\$stack = new MyStack();
\$stack->push(1);
\$stack->push(2);
\$stack->push(3);
\$stack->push(4);
\$stack->push(5);
\$stack->push(6);
\$stack->push(7);
\$stack->push(8);
/*
Constructed stack
==========
8  <-- Top
7
6
5
4
3
2
1
*/
// Display stack elements
echo " Before Reverse \n";
// Perform reverse operation
/*
After reverse
==========
1  <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
echo "\n After Reverse \n";
}
main();``````

#### Output

`````` Before Reverse
8  7  6  5  4  3  2  1

After Reverse
1  2  3  4  5  6  7  8``````
``````/*
Node Js Program
The Stock Span Problem
*/
// 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 ReverseElements
{
// Print element of stack
printData(stack)
{
var temp = stack.top;
// iterate stack elements
while (temp != null)
{
// Display element value
process.stdout.write("  " + temp.element);
temp = temp.next;
}
process.stdout.write("\n");
}
// Transfer all stack t1 data into a stack t2
transferData(t1, t2)
{
var data = 0;
// Executing the loop until when t1 stack element are not empty
while (t1.isEmpty() == false)
{
// Get the top element of t1 stack
data = t1.peek();
// Remove top of current t1 stack
t1.pop();
// Add data to t2 stack
t2.push(data);
}
}
// This is reverse the stack elements by using of auxiliary stacks
reverseStack(stack)
{
// Create two auxiliary stacks
var auxiliary1 = new MyStack();
var auxiliary2 = new MyStack();
// Send the all elements from actual stack into auxiliary1
this.transferData(stack, auxiliary1);
// Send the all elements from auxiliary1 into auxiliary2
this.transferData(auxiliary1, auxiliary2);
// Send the all elements from auxiliary2 into actual stack
this.transferData(auxiliary2, stack);
}
}

function main()
{
// Create a stack
var stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
/*
Constructed stack
==========
8  <-- Top
7
6
5
4
3
2
1
*/
// Display stack elements
process.stdout.write(" Before Reverse \n");
// Perform reverse operation
/*
After reverse
==========
1  <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
process.stdout.write("\n After Reverse \n");
}
main();``````

#### Output

`````` Before Reverse
8  7  6  5  4  3  2  1

After Reverse
1  2  3  4  5  6  7  8``````
``````# Python 3 Program
# The Stock Span Problem

#  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 ReverseElements :
#  Print element of stack
def printData(self, stack) :
temp = stack.top
#  iterate stack elements
while (temp != None) :
#  Display element value
print("  ", temp.element, end = "")
temp = temp.next

print(end = "\n")

#  Transfer all stack t1 data into a stack t2
def transferData(self, t1, t2) :
data = 0
#  Executing the loop until when t1 stack element are not empty
while (t1.isEmpty() == False) :
#  Get the top element of t1 stack
data = t1.peek()
#  Remove top of current t1 stack
t1.pop()
#  Add data to t2 stack
t2.push(data)

#  This is reverse the stack elements by using of auxiliary stacks
def reverseStack(self, stack) :
#  Create two auxiliary stacks
auxiliary1 = MyStack()
auxiliary2 = MyStack()
#  Send the all elements from actual stack into auxiliary1
self.transferData(stack, auxiliary1)
#  Send the all elements from auxiliary1 into auxiliary2
self.transferData(auxiliary1, auxiliary2)
#  Send the all elements from auxiliary2 into actual stack
self.transferData(auxiliary2, stack)

def main() :
#  Create a stack
stack = MyStack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
stack.push(6)
stack.push(7)
stack.push(8)
#
#         Constructed stack
#         ==========
#             8  <-- Top
#             7
#             6
#             5
#             4
#             3
#             2
#             1
#

#  Display stack elements
print(" Before Reverse ")
#  Perform reverse operation
#
#         After reverse
#         ==========
#             1  <-- Top
#             2
#             3
#             4
#             5
#             6
#             7
#             8
#

#  Display stack elements
print("\n After Reverse ")

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

#### Output

`````` Before Reverse
8   7   6   5   4   3   2   1

After Reverse
1   2   3   4   5   6   7   8``````
``````#  Ruby Program
#  The Stock Span Problem

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

def initialize(element, top)
self.element = element
self.next = top
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 ReverseElements
#  Print element of stack
def printData(stack)
temp = stack.top
#  iterate stack elements
while (temp != nil)
#  Display element value
print("  ", temp.element)
temp = temp.next
end

print("\n")
end

#  Transfer all stack t1 data into a stack t2
def transferData(t1, t2)
data = 0
#  Executing the loop until when t1 stack element are not empty
while (t1.isEmpty() == false)
#  Get the top element of t1 stack
data = t1.peek()
#  Remove top of current t1 stack
t1.pop()
#  Add data to t2 stack
t2.push(data)
end

end

#  This is reverse the stack elements by using of auxiliary stacks
def reverseStack(stack)
#  Create two auxiliary stacks
auxiliary1 = MyStack.new()
auxiliary2 = MyStack.new()
#  Send the all elements from actual stack into auxiliary1
self.transferData(stack, auxiliary1)
#  Send the all elements from auxiliary1 into auxiliary2
self.transferData(auxiliary1, auxiliary2)
#  Send the all elements from auxiliary2 into actual stack
self.transferData(auxiliary2, stack)
end

end

def main()
#  Create a stack
stack = MyStack.new()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
stack.push(6)
stack.push(7)
stack.push(8)
#
#         Constructed stack
#         ==========
#             8  <-- Top
#             7
#             6
#             5
#             4
#             3
#             2
#             1
#

#  Display stack elements
print(" Before Reverse \n")
#  Perform reverse operation
#
#         After reverse
#         ==========
#             1  <-- Top
#             2
#             3
#             4
#             5
#             6
#             7
#             8
#

#  Display stack elements
print("\n After Reverse \n")
end

main()``````

#### Output

`````` Before Reverse
8  7  6  5  4  3  2  1

After Reverse
1  2  3  4  5  6  7  8
``````
``````/*
Scala Program
The Stock Span Problem
*/
// 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 ReverseElements
{
// Print element of stack
def printData(stack: MyStack): Unit = {
var temp: StackNode = stack.top;
// iterate stack elements
while (temp != null)
{
// Display element value
print("  " + temp.element);
temp = temp.next;
}
print("\n");
}
// Transfer all stack t1 data into a stack t2
def transferData(t1: MyStack, t2: MyStack): Unit = {
var data: Int = 0;
// Executing the loop until when t1 stack element are not empty
while (t1.isEmpty() == false)
{
// Get the top element of t1 stack
data = t1.peek();
// Remove top of current t1 stack
t1.pop();
// Add data to t2 stack
t2.push(data);
}
}
// This is reverse the stack elements by using of auxiliary stacks
def reverseStack(stack: MyStack): Unit = {
// Create two auxiliary stacks
var auxiliary1: MyStack = new MyStack();
var auxiliary2: MyStack = new MyStack();
// Send the all elements from actual stack into auxiliary1
this.transferData(stack, auxiliary1);
// Send the all elements from auxiliary1 into auxiliary2
this.transferData(auxiliary1, auxiliary2);
// Send the all elements from auxiliary2 into actual stack
this.transferData(auxiliary2, stack);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: ReverseElements = new ReverseElements();
// Create a stack
var stack: MyStack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
/*
Constructed stack
==========
8  <-- Top
7
6
5
4
3
2
1
*/
// Display stack elements
print(" Before Reverse \n");
// Perform reverse operation
/*
After reverse
==========
1  <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
print("\n After Reverse \n");
}
}``````

#### Output

`````` Before Reverse
8  7  6  5  4  3  2  1

After Reverse
1  2  3  4  5  6  7  8``````
``````/*
Swift 4 Program
The Stock Span Problem
*/
// 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 ReverseElements
{
// Print element of stack
func printData(_ stack: MyStack)
{
var temp: StackNode? = stack.top;
// iterate stack elements
while (temp != nil)
{
// Display element value
print("  ", temp!.element, terminator: "");
temp = temp!.next;
}
print(terminator: "\n");
}
// Transfer all stack t1 data into a stack t2
func transferData(_ t1: MyStack, _ t2: MyStack)
{
var data: Int = 0;
// Executing the loop until when t1 stack element are not empty
while (t1.isEmpty() == false)
{
// Get the top element of t1 stack
data = t1.peek();
// Remove top of current t1 stack
t1.pop();
// Add data to t2 stack
t2.push(data);
}
}
// This is reverse the stack elements by using of auxiliary stacks
func reverseStack(_ stack: MyStack )
{
// Create two auxiliary stacks
let auxiliary1: MyStack = MyStack();
let auxiliary2: MyStack = MyStack();
// Send the all elements from actual stack into auxiliary1
self.transferData(stack, auxiliary1);
// Send the all elements from auxiliary1 into auxiliary2
self.transferData(auxiliary1, auxiliary2);
// Send the all elements from auxiliary2 into actual stack
self.transferData(auxiliary2, stack);
}
}
func main()
{
// Create a stack
let stack: MyStack = MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
/*
Constructed stack
==========
8  <-- Top
7
6
5
4
3
2
1
*/
// Display stack elements
print(" Before Reverse ");
// Perform reverse operation
/*
After reverse
==========
1  <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
print("\n After Reverse ");
}
main();``````

#### Output

`````` Before Reverse
8   7   6   5   4   3   2   1

After Reverse
1   2   3   4   5   6   7   8``````
``````/*
Kotlin Program
The Stock Span Problem
*/
// 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 ReverseElements
{
// Print element of stack
fun printData(stack: MyStack): Unit
{
var temp: StackNode ? = stack.top;
// iterate stack elements
while (temp != null)
{
// Display element value
print("  " + temp.element);
temp = temp.next;
}
print("\n");
}
// Transfer all stack t1 data into a stack t2
fun transferData(t1: MyStack , t2 : MyStack ): Unit
{
var data: Int ;
// Executing the loop until when t1 stack element are not empty
while (t1.isEmpty() == false)
{
// Get the top element of t1 stack
data = t1.peek();
// Remove top of current t1 stack
t1.pop();
// Add data to t2 stack
t2.push(data);
}
}
// This is reverse the stack elements by using of auxiliary stacks
fun reverseStack(stack: MyStack): Unit
{
// Create two auxiliary stacks
var auxiliary1: MyStack = MyStack();
var auxiliary2: MyStack = MyStack();
// Send the all elements from actual stack into auxiliary1
this.transferData(stack, auxiliary1);
// Send the all elements from auxiliary1 into auxiliary2
this.transferData(auxiliary1, auxiliary2);
// Send the all elements from auxiliary2 into actual stack
this.transferData(auxiliary2, stack);
}
}
fun main(args: Array<String>): Unit
{
// Create a stack
var stack: MyStack = MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
/*
Constructed stack
==========
8  <-- Top
7
6
5
4
3
2
1
*/
// Display stack elements
print(" Before Reverse \n");
// Perform reverse operation
/*
After reverse
==========
1  <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
print("\n After Reverse \n");
}``````

#### Output

`````` Before Reverse
8  7  6  5  4  3  2  1

After Reverse
1  2  3  4  5  6  7  8``````

## Time Complexity

The time complexity of the algorithm is O(n^2) in the worst case, where n is the number of elements in the original stack. This is because the algorithm performs nested loops to find the minimum element, which takes O(n) time, and there are n elements to be sorted.

## Resultant Output Explanation

For the given example stack:

``````8
7
6
5
4
3
2
1``````

The output shows the sorted stack in ascending order:

``````1
2
3
4
5
6
7
8
``````

The output demonstrates that the stack has been successfully sorted using the two auxiliary stacks-based sorting algorithm.

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