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.
- We create two auxiliary stacks, say
auxiliary1
andauxiliary2
. - We transfer all the elements from the original stack to
auxiliary1
. - We find the minimum element in
auxiliary1
, pop it, and push it intoauxiliary2
. - We repeat this process until
auxiliary1
is empty. - The elements in
auxiliary2
are now in ascending order. - 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
- The
transferData
function takes two stackst1
andt2
as input and transfers all the elements fromt1
tot2
in their original order. - The
reverseStack
function creates two auxiliary stacks,auxiliary1
andauxiliary2
. - It transfers all the elements from the original stack to
auxiliary1
using thetransferData
function. - While
auxiliary1
is not empty, it finds the minimum element inauxiliary1
, pops it fromauxiliary1
, and pushes it intoauxiliary2
. - This process is repeated until
auxiliary1
becomes empty, andauxiliary2
now contains the elements of the original stack in ascending order. - Finally, the
transferData
function is used again to transfer all the elements fromauxiliary2
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)
{
// Add stack element
stack->top = newNode(element, stack->top);
stack->size++;
}
// return top element of stack
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();
// Add elements
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--;
}
}
// return top element of stack
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)
{
ReverseElements task = new ReverseElements();
// Create a stack
MyStack stack = new MyStack();
// Add elements
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");
task.printData(stack);
// Perform reverse operation
task.reverseStack(stack);
/*
After reverse
==========
1 <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
System.out.print("\n After Reverse \n");
task.printData(stack);
}
}
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--;
}
}
// return top element of stack
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()
{
ReverseElements task = ReverseElements();
// Create a stack
MyStack stack = MyStack();
// Add elements
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";
task.printData(stack);
// Perform reverse operation
task.reverseStack(stack);
/*
After reverse
==========
1 <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
cout << "\n After Reverse \n";
task.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
// 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--;
}
}
// return top element of stack
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)
{
ReverseElements task = new ReverseElements();
// Create a stack
MyStack stack = new MyStack();
// Add elements
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");
task.printData(stack);
// Perform reverse operation
task.reverseStack(stack);
/*
After reverse
==========
1 <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
Console.Write("\n After Reverse \n");
task.printData(stack);
}
}
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--;
}
}
// return top element of stack
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()
{
$task = new ReverseElements();
// Create a stack
$stack = new MyStack();
// Add elements
$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";
$task->printData($stack);
// Perform reverse operation
$task->reverseStack($stack);
/*
After reverse
==========
1 <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
echo "\n After Reverse \n";
$task->printData($stack);
}
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--;
}
}
// return top element of stack
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()
{
var task = new ReverseElements();
// Create a stack
var stack = new MyStack();
// Add elements
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");
task.printData(stack);
// Perform reverse operation
task.reverseStack(stack);
/*
After reverse
==========
1 <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
process.stdout.write("\n After Reverse \n");
task.printData(stack);
}
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
# return top element of stack
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() :
task = ReverseElements()
# Create a stack
stack = MyStack()
# Add elements
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 ")
task.printData(stack)
# Perform reverse operation
task.reverseStack(stack)
#
# After reverse
# ==========
# 1 <-- Top
# 2
# 3
# 4
# 5
# 6
# 7
# 8
#
# Display stack elements
print("\n After Reverse ")
task.printData(stack)
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_reader :element, :next
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_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 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()
task = ReverseElements.new()
# Create a stack
stack = MyStack.new()
# Add elements
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")
task.printData(stack)
# Perform reverse operation
task.reverseStack(stack)
#
# After reverse
# ==========
# 1 <-- Top
# 2
# 3
# 4
# 5
# 6
# 7
# 8
#
# Display stack elements
print("\n After Reverse \n")
task.printData(stack)
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;
}
}
// return top element of stack
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();
// Add elements
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");
task.printData(stack);
// Perform reverse operation
task.reverseStack(stack);
/*
After reverse
==========
1 <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
print("\n After Reverse \n");
task.printData(stack);
}
}
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;
}
}
// return top element of stack
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()
{
let task: ReverseElements = ReverseElements();
// Create a stack
let stack: MyStack = MyStack();
// Add elements
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 ");
task.printData(stack);
// Perform reverse operation
task.reverseStack(stack);
/*
After reverse
==========
1 <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
print("\n After Reverse ");
task.printData(stack);
}
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;
}
}
// return top element of stack
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
{
var task: ReverseElements = ReverseElements();
// Create a stack
var stack: MyStack = MyStack();
// Add elements
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");
task.printData(stack);
// Perform reverse operation
task.reverseStack(stack);
/*
After reverse
==========
1 <-- Top
2
3
4
5
6
7
8
*/
// Display stack elements
print("\n After Reverse \n");
task.printData(stack);
}
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.
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