Skip to main content

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

  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);
	//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 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.

Last updated on by Kalkicode




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.

New Comment