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
add_element(stack record, int item):
if record is empty:
push item to the stack
return
data = top element of stack
pop the top element
add_element(record, item)
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)
add_element(record, data)
Algorithm Explanation
- 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. - 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. - 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 theadd_element
function.
Resultant Output Explanation
- The
main
function creates a stack and adds elements [2, 3, 6, 1, 9, 8] to it. - It then calls the
display_stack
function, which prints the original stack as "8 9 1 6 3 2". - Next, the
reverse_stack
function is called, which reverses the stack. - 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);
//Add back to stack
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();
add_element(record, item);
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
add_element(record, data);
}
}
int main()
{
//Define a stack of integer elements
stack < int > record;
//Add stack elements
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();
//Add back to stack
record.push(data);
}
//Add a new stack elements into reversal stack
public void add_element(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.peek();
//Remove top element of stack
record.pop();
add_element(item);
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
add_element(data);
}
}
public void add_record()
{
//Add stack elements
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();
obj.add_record();
//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();
//Add back to stack
record.Push(data);
}
//Add a new stack elements into reversal stack
public void add_element(int item)
{
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();
add_element(item);
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
add_element(data);
}
}
public void add_record()
{
//Add stack elements
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();
obj.add_record();
//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();
//Add back to stack
$this->push($data);
}
//Add a new stack elements into reversal stack
public function add_element($item)
{
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->add_element($item);
$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->add_element($data);
}
}
public function add_record()
{
//Add stack elements
$this->push(2);
$this->push(3);
$this->push(6);
$this->push(1);
$this->push(9);
$this->push(8);
}
}
function main()
{
$obj = new ReverseStack();
$obj->add_record();
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();
//Add back to 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
add_element(item)
{
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.add_element(item);
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.add_element(data);
}
}
add_record()
{
//Add stack elements
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();
obj.add_record();
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()
# Add back to stack
self.push(data)
# Add a new stack elements into reversal stack
def add_element(self, item) :
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.add_element(item)
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.add_element(data)
def add_record(self) :
# Add stack elements
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()
obj.add_record()
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_reader :record
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()
# Add back to stack
self.push(data)
end
# Add a new stack elements into reversal stack
def add_element(item)
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.add_element(item)
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
self.add_element(data)
end
end
def add_record()
# Add stack elements
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()
obj.add_record()
# 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();
//Add back to 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();
add_element(item);
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
add_element(data);
}
}
def add_record(): Unit = {
//Add stack elements
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();
obj.add_record();
//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 bothpop
andadd_element
functions, which perform N operations as well. Hence, the time complexity forreverse_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.
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