Posted on by Kalkicode
Code Recursion

# Reverse stack using recursion

The problem of reversing a stack using recursion involves reversing the order of elements in a stack without using any additional data structures. A stack is a data structure that follows the Last In First Out (LIFO) principle, meaning the last element inserted is the first one to be removed. Reversing a stack would mean that the top element becomes the bottom, and the bottom element becomes the top.

## Problem Statement:

Given a stack of integers, we are tasked with reversing the order of its elements using recursion. We need to implement functions to display the stack elements, add a new element into the reversed stack, and finally, reverse the stack.

## Example:

Consider a stack with the following elements: [2, 3, 6, 1, 9, 8]. The original stack is displayed as: "8 9 1 6 3 2". After applying the reverse operation, the stack becomes: "2 3 6 1 9 8".

## Pseudocode

Below is the pseudocode for the three main functions: `display_stack`, `add_element`, and `reverse_stack`, required to reverse the stack.

``````display_stack(stack record):
if record is empty:
return
data = top element of stack
pop the top element
print data
display_stack(record)
push data back to the stack

if record is empty:
push item to the stack
return
data = top element of stack
pop the top element
push data back to the stack

reverse_stack(stack record):
if record is empty:
return
else:
data = top element of stack
pop the top element
reverse_stack(record)
``````

## Algorithm Explanation

1. The `display_stack` function recursively prints the elements of the stack by taking the top element, printing it, and then calling itself on the rest of the stack.
2. The `add_element` function recursively adds a new element to the reversed stack by first removing the top element from the original stack, then calling itself with the new element, and finally pushing back the removed element.
3. The `reverse_stack` function reverses the original stack by taking the top element, removing it, recursively reversing the remaining stack, and finally adding the top element back using the `add_element` function.

## Resultant Output Explanation

1. The `main` function creates a stack and adds elements [2, 3, 6, 1, 9, 8] to it.
2. It then calls the `display_stack` function, which prints the original stack as "8 9 1 6 3 2".
3. Next, the `reverse_stack` function is called, which reverses the stack.
4. Finally, the `display_stack` function is called again to display the reversed stack, which appears as "2 3 6 1 9 8".

## Program Solution

``````// C++ program for
// Reverse stack using recursion
#include <iostream>

#include <stack>

using namespace std;
//Display stack elements
void display_stack(stack < int > & record)
{
if (record.size() == 0)
{
return;
}
int data = record.top();
//Remove top element
record.pop();
cout << " " << data;
//Recursive calling process
display_stack(record);
record.push(data);
}
//Add a new stack elements into reversal stack
void add_element(stack < int > & record, int item)
{
if (record.size() == 0)
{
//When stack is empty add a new element
record.push(item);
return;
}
//Get top element of stack
int data = record.top();
//Remove top element of stack
record.pop();
record.push(data);
}
//Reverse a stack elements
void reverse_stack(stack < int > & record)
{
if (record.size() == 0)
{
//When stack is empty
return;
}
else
{
int data = record.top();
//Remove top element of stack
record.pop();
reverse_stack(record);
//append data into stack
}
}
int main()
{
//Define a stack of integer elements
stack < int > record;
record.push(2);
record.push(3);
record.push(6);
record.push(1);
record.push(9);
record.push(8);
cout << "\n Stack element : ";
display_stack(record);
reverse_stack(record);
cout << "\n Stack element : ";
display_stack(record);
return 0;
}``````

#### Output

`````` Stack element :  8 9 1 6 3 2
Stack element :  2 3 6 1 9 8``````
``````// Java Program
// Reverse stack using recursion
import java.util.Stack;
class ReverseStack
{
public Stack < Integer > record;
public ReverseStack()
{
record = new Stack < > ();
}
//Display stack elements
public void display_stack()
{
if (this.record.size() == 0)
{
return;
}
int data = this.record.peek();
//Remove top element
this.record.pop();
System.out.print(" " + data);
//Recursive calling process
display_stack();
record.push(data);
}
//Add a new stack elements into reversal stack
{
if (record.size() == 0)
{
//When stack is empty add a new element
record.push(item);
return;
}
//Get top element of stack
int data = record.peek();
//Remove top element of stack
record.pop();
record.push(data);
}
//Reverse a stack elements
public void reverse_stack()
{
if (record.size() == 0)
{
//When stack is empty
return;
}
else
{
int data = record.peek();
//Remove top element of stack
record.pop();
reverse_stack();
//append data into stack
}
}
{
this.record.push(2);
this.record.push(3);
this.record.push(6);
this.record.push(1);
this.record.push(9);
this.record.push(8);
}
public static void main(String[] args)
{
ReverseStack obj = new ReverseStack();
//Before
System.out.print("\n Stack element : ");
obj.display_stack();
//Reverse Element
obj.reverse_stack();
//After
System.out.print("\n Stack element : ");
obj.display_stack();
}
}``````

#### Output

`````` Stack element :  8 9 1 6 3 2
Stack element :  2 3 6 1 9 8``````
``````//Include namespace system
using System;
using System.Collections;
class ReverseStack
{
public Stack record = null;
public ReverseStack()
{
record = new Stack();
}
//Display stack elements
public void display_stack()
{
if (this.record.Count == 0)
{
return;
}
int data = (int)this.record.Peek();
//Remove top element
this.record.Pop();
Console.Write(" " + data);
//Recursive calling process
display_stack();
record.Push(data);
}
//Add a new stack elements into reversal stack
{
if (record.Count == 0)
{
//When stack is empty add a new element
record.Push(item);
return;
}
//Get top element of stack
int data = (int)record.Peek();
//Remove top element of stack
record.Pop();
record.Push(data);
}
//Reverse a stack elements
public void reverse_stack()
{
if (record.Count == 0)
{
//When stack is empty
return;
}
else
{
int data = (int)record.Peek();
//Remove top element of stack
record.Pop();
reverse_stack();
//append data into stack
}
}
{
this.record.Push(2);
this.record.Push(3);
this.record.Push(6);
this.record.Push(1);
this.record.Push(9);
this.record.Push(8);
}
public static void Main(String[] args)
{
ReverseStack obj = new ReverseStack();
//Before
Console.Write("\n Stack element : ");
obj.display_stack();
//Reverse Element
obj.reverse_stack();
//After
Console.Write("\n Stack element : ");
obj.display_stack();
}
}``````

#### Output

`````` Stack element :  8 9 1 6 3 2
Stack element :  2 3 6 1 9 8``````
``````<?php
// Php Program
// Reverse stack using recursion
class ReverseStack
{
public \$record;

function __construct()
{
//Create a custom stack
\$this->record = array();
}
public function push(\$data)
{

//Add element at beginning of stack
array_unshift(\$this->record, \$data);

}
public function pop()
{

// Check whether stack array is empty or not
if (count(\$this->record)==0)
{
// When try of remove a element in empty stack
echo ("Stack Empty");
return;
}
else
{

return array_shift(\$this->record);
}
}
public function peek() {

// Check whether stack array is empty or not
if (count(\$this->record)==0)
{
// When try of remove a element in empty stack
echo ("Stack Empty");

} else
{

return \$this->record[0];
}
}
//Display stack elements
public  function display_stack()
{
if (count(\$this->record) == 0)
{
return;
}
\$data = \$this->peek();
//Remove top element
\$this->pop();
echo " ". \$data;
//Recursive calling process
\$this->display_stack();
\$this->push(\$data);
}
//Add a new stack elements into reversal stack
{
if (count(\$this->record) == 0)
{
//When stack is empty add a new element
\$this->push(\$item);
return;
}
//Get top element of stack
\$data = \$this->peek();
//Remove top element of stack
\$this->pop();
\$this->push(\$data);
}
//Reverse a stack elements
public  function reverse_stack()
{
if (count(\$this->record) == 0)
{
//When stack is empty
return;
}
else
{
\$data = \$this->peek();
//Remove top element of stack
\$this->pop();
\$this->reverse_stack();
//append data into stack
}
}
{

\$this->push(2);
\$this->push(3);
\$this->push(6);
\$this->push(1);
\$this->push(9);
\$this->push(8);

}
}

function main()
{
\$obj = new ReverseStack();
echo "\n Stack element : ";
\$obj->display_stack();
//Reverse Element
\$obj->reverse_stack();
echo "\n Stack element : ";
\$obj->display_stack();
}
main();``````

#### Output

`````` Stack element :  8 9 1 6 3 2
Stack element :  2 3 6 1 9 8``````
``````// Node JS program for
// Reverse stack using recursion
class ReverseStack
{
constructor()
{
this.record = [];
}
//Display stack elements
display_stack()
{
if (this.record.length == 0)
{
return;
}
var data = this.peek();
//Remove top element
this.record.pop();
process.stdout.write(" " + data);
//Recursive calling process
this.display_stack();
this.record.push(data);
}
peek()
{
if (this.record.length == 0)
{
return;
}
else
{
return this.record[this.record.length - 1];
}
}
//Add a new stack elements into reversal stack
{
if (this.record.length == 0)
{
//When stack is empty add a new element
this.record.push(item);
return;
}
//Get top element of stack
var data = this.peek();
//Remove top element of stack
this.record.pop();
this.record.push(data);
}
//Reverse a stack elements
reverse_stack()
{
if (this.record.length == 0)
{
//When stack is empty
return;
}
else
{
var data = this.peek();
//Remove top element of stack
this.record.pop();
this.reverse_stack();
//append data into stack
}
}
{
this.record.push(2);
this.record.push(3);
this.record.push(6);
this.record.push(1);
this.record.push(9);
this.record.push(8);
}
}

function main()
{
var obj = new ReverseStack();
process.stdout.write("\n Stack element : ");
obj.display_stack();
//Reverse Element
obj.reverse_stack();
process.stdout.write("\n Stack element : ");
obj.display_stack();
}
main();``````

#### Output

`````` Stack element :  8 9 1 6 3 2
Stack element :  2 3 6 1 9 8``````
``````#  Python 3 Program
#  Reverse stack using recursion
class ReverseStack :
def __init__(self) :
self.record = []

# Display stack elements
def display_stack(self) :
if (len(self.record)==0) :
return

data = self.peek()
# Remove top element
self.pop()
print(" ", data, end = "")
# Recursive calling process
self.display_stack()
self.push(data)

# Add a new stack elements into reversal stack
if (len(self.record)==0) :
# When stack is empty add a new element
self.push(item)
return

# Get top element of stack
data = self.peek()
# Remove top element of stack
self.pop()
self.push(data)

# Reverse a stack elements
def reverse_stack(self) :
if (len(self.record)==0) :
# When stack is empty
return
else :
data = self.peek()
# Remove top element of stack
self.pop()
self.reverse_stack()
# append data into stack

self.push(2)
self.push(3)
self.push(6)
self.push(1)
self.push(9)
self.push(8)

def push(self,data) :
self.record.insert(0, data)

def pop(self) :
if(len(self.record)==0) :
print ("Stack empty")
return

self.record.pop(0)

def peek(self) :
if(len(self.record)==0) :
print ("Stack empty")
return

return self.record[0]
def main() :
obj = ReverseStack()
print("\n Stack element : ", end = "")
obj.display_stack()
# Reverse Element
obj.reverse_stack()
print("\n Stack element : ", end = "")
obj.display_stack()

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

#### Output

`````` Stack element :   8  9  1  6  3  2
Stack element :   2  3  6  1  9  8``````
``````#  Ruby Program
#  Reverse stack using recursion
class ReverseStack

# Define the accessor and reader of class ReverseStack
attr_accessor :record

def initialize()
@record = []
end

# Get top element
def peek()

if (self.record.length == 0)
print("Empty Stack\n")
return
end
return self.record[0]
end
# remove top element
def pop()

if (self.record.length == 0)
print("Empty Stack\n")
return
end

self.record.shift
end
# push
def push(data)

self.record = [data] + self.record
end
# Display stack elements
def display_stack()

if (self.record.length == 0)

return
end
data = self.peek()
# Remove top element
self.pop()
print(" ", data)
# Recursive calling process
self.display_stack()
self.push(data)
end
# Add a new stack elements into reversal stack

if (self.record.length == 0)

# When stack is empty add a new element
self.push(item)
return
end
# Get top element of stack
data = self.peek()
# Remove top element of stack
self.pop()
self.push(data)
end
# Reverse a stack elements
def reverse_stack()

if (self.record.length == 0)

# When stack is empty
return
else

data = self.peek()
# Remove top element of stack
self.pop()
self.reverse_stack()
# append data into stack
end
end

self.push(2)
self.push(3)
self.push(6)
self.push(1)
self.push(9)
self.push(8)

end
end
def main()

obj = ReverseStack.new()
# Before
print("\n Stack element : ")
obj.display_stack()
# Reverse Element
obj.reverse_stack()
# After
print("\n Stack element : ")
obj.display_stack()
end
main()``````

#### Output

`````` Stack element :  8 9 1 6 3 2
Stack element :  2 3 6 1 9 8``````
``````// Scala Program
// Reverse stack using recursion
import scala.collection.mutable.Stack
class ReverseStack(var record: Stack[Int] )
{
def this()
{
this(Stack[Int]());
}
//Display stack elements
def display_stack(): Unit = {
if (this.record.isEmpty)
{
return;
}
var data: Int = this.record.top;
//Remove top element
this.record.pop();
print(" " + data);
//Recursive calling process
display_stack();
record.push(data);
}
//Add a new stack elements into reversal stack
def add_element(item: Int): Unit = {
if (this.record.isEmpty)
{
//When stack is empty add a new element
record.push(item);
return;
}
//Get top element of stack
var data: Int = record.top;
//Remove top element of stack
record.pop();
record.push(data);
}
//Reverse a stack elements
def reverse_stack(): Unit = {
if (this.record.isEmpty)
{
//When stack is empty
return;
}
else
{
var data: Int = record.top;
//Remove top element of stack
record.pop();
reverse_stack();
//append data into stack
}
}
this.record.push(2);
this.record.push(3);
this.record.push(6);
this.record.push(1);
this.record.push(9);
this.record.push(8);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: ReverseStack = new ReverseStack();
//Before
print("\n Stack element : ");
obj.display_stack();
//Reverse Element
obj.reverse_stack();
//After
print("\n Stack element : ");
obj.display_stack();
}
}``````

#### Output

`````` Stack element :  8 9 1 6 3 2
Stack element :  2 3 6 1 9 8``````

## Time Complexity Analysis

The time complexity of this approach can be analyzed based on the number of operations performed on the stack.

• The `display_stack` function performs N recursive calls, where N is the number of elements in the stack. The time complexity for this function is O(N).
• The `add_element` function also performs N recursive calls in the worst case, giving a time complexity of O(N).
• The `reverse_stack` function calls both `pop` and `add_element` functions, which perform N operations as well. Hence, the time complexity for `reverse_stack` is O(N).

Overall, the time complexity of reversing the stack using recursion is O(N), where N is the number of elements in the stack.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post