Reverse stack using another stack
The problem of Reverse Stack using Another Stack involves reversing the elements of a given stack using only one additional auxiliary stack. The task is to implement a function that takes an original stack as input and reverses its elements so that the top element becomes the bottom element and vice versa.
Problem Statement
Given a stack, implement a function reverseStack()
that reverses the order of its elements using
another auxiliary stack. The original stack should be modified in-place, and the auxiliary stack should be used
to achieve the reversal.
Example
Consider the following stack:
11 <- Top
9
6
5
4
2
1
After reversing the stack using another stack, the result should be:
1 <- Top
2
4
5
6
9
11
Idea to Solve the Problem
To reverse the stack using another stack, we can use the following approach:
- Create an auxiliary stack to store the reversed elements.
- While the original stack is not empty, perform the following steps:
- Pop the top element
data
from the original stack. - Push
data
onto the auxiliary stack.
- Pop the top element
- After all elements are processed, the auxiliary stack will contain the elements of the original stack in reversed order.
- Set the original stack to be equal to the auxiliary stack. Now, the original stack contains the elements in the reversed order.
Pseudocode
Function reverseStack():
Create a new MyStack called auxiliary
While stack is not empty:
Pop the top element data from stack
Push data onto auxiliary
Set stack to be equal to auxiliary
Code Solution
// C program
// Reverse stack using another 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 *newStack()
{
//Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
//Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
}
//Create a new node of stack
struct StackNode *newNode(int element, struct StackNode *next)
{
//Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->element = element;
node->next = next;
}
return node;
}
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{
// Add stack element
stack->top = newNode(element, stack->top);
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--;
}
}
// This is reverse the stack elements by using of another stack
void reverseStack(struct MyStack *stack)
{
// Create auxiliary stack
struct MyStack *auxiliary = newStack();
int data;
// Executing the loop until when input element are not empty
while (isEmpty(stack) == 0)
{
// Get the top element of input stack
data = peek(stack);
// Remove top of current input stack
pop(stack);
// Add data to auxiliary stack
push(auxiliary, data);
}
// Set auxiliary stack as new stack
stack->top = auxiliary->top;
}
// 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();
// Add the stack element
push(stack, 1);
push(stack, 2);
push(stack, 4);
push(stack, 5);
push(stack, 6);
push(stack, 9);
push(stack, 11);
printf("\n Before Reverse \n");
printData(stack);
// reverse operation
reverseStack(stack);
printf("\n After Reverse \n");
printData(stack);
return 0;
}
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
/*
Java Program
Reverse stack using another stack
*/
// Define stack node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
return this.top.element;
}
}
public class 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");
}
// This is reverse the stack elements by using of another stack
public void reverseStack()
{
// Create auxiliary stack
MyStack auxiliary = new MyStack();
int data = 0;
// Executing the loop until when input element are not empty
while (this.stack.isEmpty() == false)
{
// Get the top element of input stack
data = this.stack.peek();
// Remove top of current input stack
this.stack.pop();
// Add data to auxiliary stack
auxiliary.push(data);
}
// Set auxiliary stack as new stack
this.stack = auxiliary;
}
public static void main(String[] args)
{
SortStackElement task = new SortStackElement();
// Add the stack element
task.stack.push(1);
task.stack.push(2);
task.stack.push(4);
task.stack.push(5);
task.stack.push(6);
task.stack.push(9);
task.stack.push(11);
/*
Before Reverse
=============
11 <- Top
9
6
5
4
2
1
*/
System.out.print("\n Before Reverse \n");
task.printData();
// reverse operation
task.reverseStack();
/*
After Reverse
=============
1 <- Top
2
4
5
6
9
11
*/
System.out.print("\n After Reverse \n");
task.printData();
}
}
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Reverse stack using another stack
*/
// Define stack node
class StackNode
{
public:
int element;
StackNode *next;
StackNode(int element, StackNode *next)
{
this->element = element;
this->next = next;
}
};
// Define a custom stack
class MyStack
{
public:
StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
delete temp;
temp = NULL;
this->size--;
}
}
// return top element of stack
int peek()
{
return this->top->element;
}
};
class SortStackElement
{
public:
MyStack stack;
SortStackElement()
{
this->stack = 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";
}
// This is reverse the stack elements by using of another stack
void reverseStack()
{
// Create auxiliary stack
MyStack auxiliary = MyStack();
int data = 0;
// Executing the loop until when input element are not empty
while (this->stack.isEmpty() == false)
{
// Get the top element of input stack
data = this->stack.peek();
// Remove top of current input stack
this->stack.pop();
// Add data to auxiliary stack
auxiliary.push(data);
}
// Set auxiliary stack as new stack
this->stack = auxiliary;
}
};
int main()
{
SortStackElement task = SortStackElement();
// Add the stack element
task.stack.push(1);
task.stack.push(2);
task.stack.push(4);
task.stack.push(5);
task.stack.push(6);
task.stack.push(9);
task.stack.push(11);
/*
Before Reverse
=============
11 <- Top
9
6
5
4
2
1
*/
cout << "\n Before Reverse \n";
task.printData();
// reverse operation
task.reverseStack();
/*
After Reverse
=============
1 <- Top
2
4
5
6
9
11
*/
cout << "\n After Reverse \n";
task.printData();
return 0;
}
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
// Include namespace system
using System;
/*
C# Program
Reverse stack using another stack
*/
// Define stack node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
return this.top.element;
}
}
public class 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");
}
// This is reverse the stack elements by using of another stack
public void reverseStack()
{
// Create auxiliary stack
MyStack auxiliary = new MyStack();
int data = 0;
// Executing the loop until when input element are not empty
while (this.stack.isEmpty() == false)
{
// Get the top element of input stack
data = this.stack.peek();
// Remove top of current input stack
this.stack.pop();
// Add data to auxiliary stack
auxiliary.push(data);
}
// Set auxiliary stack as new stack
this.stack = auxiliary;
}
public static void Main(String[] args)
{
SortStackElement task = new SortStackElement();
// Add the stack element
task.stack.push(1);
task.stack.push(2);
task.stack.push(4);
task.stack.push(5);
task.stack.push(6);
task.stack.push(9);
task.stack.push(11);
/*
Before Reverse
=============
11 <- Top
9
6
5
4
2
1
*/
Console.Write("\n Before Reverse \n");
task.printData();
// reverse operation
task.reverseStack();
/*
After Reverse
=============
1 <- Top
2
4
5
6
9
11
*/
Console.Write("\n After Reverse \n");
task.printData();
}
}
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
<?php
/*
Php Program
Reverse stack using another stack
*/
// Define stack node
class StackNode
{
public $element;
public $next;
function __construct($element, $next)
{
$this->element = $element;
$this->next = $next;
}
}
// Define a custom stack
class MyStack
{
public $top;
public $size;
function __construct()
{
// Set node values
$this->top = null;
$this->size = 0;
}
// Add node at the top of stack
public function push($element)
{
$this->top = new StackNode($element, $this->top);
$this->size++;
}
public function isEmpty()
{
if ($this->size > 0 && $this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public function pop()
{
if ($this->size > 0 && $this->top != null)
{
$temp = $this->top;
// Change top element of stack
$this->top = $temp->next;
// remove previous top
$temp = null;
$this->size--;
}
}
// return top element of stack
public function peek()
{
return $this->top->element;
}
}
class 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";
}
// This is reverse the stack elements by using of another stack
public function reverseStack()
{
// Create auxiliary stack
$auxiliary = new MyStack();
$data = 0;
// Executing the loop until when input element are not empty
while ($this->stack->isEmpty() == false)
{
// Get the top element of input stack
$data = $this->stack->peek();
// Remove top of current input stack
$this->stack->pop();
// Add data to auxiliary stack
$auxiliary->push($data);
}
// Set auxiliary stack as new stack
$this->stack = $auxiliary;
}
}
function main()
{
$task = new SortStackElement();
// Add the stack element
$task->stack->push(1);
$task->stack->push(2);
$task->stack->push(4);
$task->stack->push(5);
$task->stack->push(6);
$task->stack->push(9);
$task->stack->push(11);
/*
Before Reverse
=============
11 <- Top
9
6
5
4
2
1
*/
echo "\n Before Reverse \n";
$task->printData();
// reverse operation
$task->reverseStack();
/*
After Reverse
=============
1 <- Top
2
4
5
6
9
11
*/
echo "\n After Reverse \n";
$task->printData();
}
main();
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
/*
Node Js Program
Reverse stack using another stack
*/
// Define stack node
class StackNode
{
constructor(element, next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
peek()
{
return this.top.element;
}
}
class 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");
}
// This is reverse the stack elements by using of another stack
reverseStack()
{
// Create auxiliary stack
var auxiliary = new MyStack();
var data = 0;
// Executing the loop until when input element are not empty
while (this.stack.isEmpty() == false)
{
// Get the top element of input stack
data = this.stack.peek();
// Remove top of current input stack
this.stack.pop();
// Add data to auxiliary stack
auxiliary.push(data);
}
// Set auxiliary stack as new stack
this.stack = auxiliary;
}
}
function main()
{
var task = new SortStackElement();
// Add the stack element
task.stack.push(1);
task.stack.push(2);
task.stack.push(4);
task.stack.push(5);
task.stack.push(6);
task.stack.push(9);
task.stack.push(11);
/*
Before Reverse
=============
11 <- Top
9
6
5
4
2
1
*/
process.stdout.write("\n Before Reverse \n");
task.printData();
// reverse operation
task.reverseStack();
/*
After Reverse
=============
1 <- Top
2
4
5
6
9
11
*/
process.stdout.write("\n After Reverse \n");
task.printData();
}
main();
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
# Python 3 Program
# Reverse stack using another stack
# Define stack node
class StackNode :
def __init__(self, element, next) :
self.element = element
self.next = next
# Define a custom stack
class MyStack :
def __init__(self) :
# Set node values
self.top = None
self.size = 0
# Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1
def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True
# Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = None
self.size -= 1
# return top element of stack
def peek(self) :
return self.top.element
class 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")
# This is reverse the stack elements by using of another stack
def reverseStack(self) :
# Create auxiliary stack
auxiliary = MyStack()
data = 0
# Executing the loop until when input element are not empty
while (self.stack.isEmpty() == False) :
# Get the top element of input stack
data = self.stack.peek()
# Remove top of current input stack
self.stack.pop()
# Add data to auxiliary stack
auxiliary.push(data)
# Set auxiliary stack as new stack
self.stack = auxiliary
def main() :
task = SortStackElement()
task.stack.push(1)
task.stack.push(2)
task.stack.push(4)
task.stack.push(5)
task.stack.push(6)
task.stack.push(9)
task.stack.push(11)
#
# Before Reverse
# =============
# 11 <- Top
# 9
# 6
# 5
# 4
# 2
# 1
#
print("\n Before Reverse ")
task.printData()
# reverse operation
task.reverseStack()
#
# After Reverse
# =============
# 1 <- Top
# 2
# 4
# 5
# 6
# 9
# 11
#
print("\n After Reverse ")
task.printData()
if __name__ == "__main__": main()
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
# Ruby Program
# Reverse stack using another stack
# Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_reader :element, :next
attr_accessor :element, :next
def initialize(element, nextNode)
self.element = element
self.next = nextNode
end
end
# Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top, :size
attr_accessor :top, :size
def initialize()
# Set node values
self.top = nil
self.size = 0
end
# Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end
def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end
end
# Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = nil
self.size -= 1
end
end
# return top element of stack
def peek()
return self.top.element
end
end
class SortStackElement
# Define the accessor and reader of class SortStackElement
attr_reader :stack
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
# This is reverse the stack elements by using of another stack
def reverseStack()
# Create auxiliary stack
auxiliary = MyStack.new()
data = 0
# Executing the loop until when input element are not empty
while (self.stack.isEmpty() == false)
# Get the top element of input stack
data = self.stack.peek()
# Remove top of current input stack
self.stack.pop()
# Add data to auxiliary stack
auxiliary.push(data)
end
# Set auxiliary stack as new stack
self.stack = auxiliary
end
end
def main()
task = SortStackElement.new()
task.stack.push(1)
task.stack.push(2)
task.stack.push(4)
task.stack.push(5)
task.stack.push(6)
task.stack.push(9)
task.stack.push(11)
#
# Before Reverse
# =============
# 11 <- Top
# 9
# 6
# 5
# 4
# 2
# 1
#
print("\n Before Reverse \n")
task.printData()
# reverse operation
task.reverseStack()
#
# After Reverse
# =============
# 1 <- Top
# 2
# 4
# 5
# 6
# 9
# 11
#
print("\n After Reverse \n")
task.printData()
end
main()
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
/*
Scala Program
Reverse stack using another stack
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode)
{
}
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: Int): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
// return top element of stack
def peek(): Int = {
return this.top.element;
}
}
class 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");
}
// This is reverse the stack elements by using of another stack
def reverseStack(): Unit = {
// Create auxiliary stack
var auxiliary: MyStack = new MyStack();
var data: Int = 0;
// Executing the loop until when input element are not empty
while (this.stack.isEmpty() == false)
{
// Get the top element of input stack
data = this.stack.peek();
// Remove top of current input stack
this.stack.pop();
// Add data to auxiliary stack
auxiliary.push(data);
}
// Set auxiliary stack as new stack
this.stack = auxiliary;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SortStackElement = new SortStackElement();
// Add the stack element
task.stack.push(1);
task.stack.push(2);
task.stack.push(4);
task.stack.push(5);
task.stack.push(6);
task.stack.push(9);
task.stack.push(11);
/*
Before Reverse
=============
11 <- Top
9
6
5
4
2
1
*/
print("\n Before Reverse \n");
task.printData();
// reverse operation
task.reverseStack();
/*
After Reverse
=============
1 <- Top
2
4
5
6
9
11
*/
print("\n After Reverse \n");
task.printData();
}
}
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
/*
Swift 4 Program
Reverse stack using another stack
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int, _ next: StackNode? )
{
self.element = element;
self.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: Int)
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
// return top element of stack
func peek()->Int
{
return self.top!.element;
}
}
class 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");
}
// This is reverse the stack elements by using of another stack
func reverseStack()
{
// Create auxiliary stack
let auxiliary: MyStack = MyStack();
var data: Int = 0;
// Executing the loop until when input element are not empty
while (self.stack.isEmpty() == false)
{
// Get the top element of input stack
data = self.stack.peek();
// Remove top of current input stack
self.stack.pop();
// Add data to auxiliary stack
auxiliary.push(data);
}
// Set auxiliary stack as new stack
self.stack = auxiliary;
}
}
func main()
{
let task: SortStackElement = SortStackElement();
// Add the stack element
task.stack.push(1);
task.stack.push(2);
task.stack.push(4);
task.stack.push(5);
task.stack.push(6);
task.stack.push(9);
task.stack.push(11);
/*
Before Reverse
=============
11 <- Top
9
6
5
4
2
1
*/
print("\n Before Reverse ");
task.printData();
// reverse operation
task.reverseStack();
/*
After Reverse
=============
1 <- Top
2
4
5
6
9
11
*/
print("\n After Reverse ");
task.printData();
}
main();
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
/*
Kotlin Program
Reverse stack using another stack
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int, next: StackNode ? )
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: Int): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean ?
{
if (this.size>0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size>0 && this.top != null)
{
var temp: StackNode ? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
// return top element of stack
fun peek(): Int
{
return this.top!!.element;
}
}
class 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");
}
// This is reverse the stack elements by using of another stack
fun reverseStack(): Unit
{
// Create auxiliary stack
var auxiliary: MyStack = MyStack();
var data: Int ;
// Executing the loop until when input element are not empty
while (this.stack.isEmpty() == false)
{
// Get the top element of input stack
data = this.stack.peek();
// Remove top of current input stack
this.stack.pop();
// Add data to auxiliary stack
auxiliary.push(data);
}
// Set auxiliary stack as new stack
this.stack = auxiliary;
}
}
fun main(args: Array<String>): Unit
{
var task: SortStackElement = SortStackElement();
// Add the stack element
task.stack.push(1);
task.stack.push(2);
task.stack.push(4);
task.stack.push(5);
task.stack.push(6);
task.stack.push(9);
task.stack.push(11);
/*
Before Reverse
=============
11 <- Top
9
6
5
4
2
1
*/
print("\n Before Reverse \n");
task.printData();
// reverse operation
task.reverseStack();
/*
After Reverse
=============
1 <- Top
2
4
5
6
9
11
*/
print("\n After Reverse \n");
task.printData();
}
Output
Before Reverse
11 9 6 5 4 2 1
After Reverse
1 2 4 5 6 9 11
Time Complexity
The time complexity of the reverseStack
function is O(N), where N is the number of elements in the
original stack. This is because we need to perform N operations (pop and push) to reverse the stack. Therefore,
the overall time complexity of the reversal process is O(N).
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