Skip to main content

Print stack in reverse order

Printing a stack in reverse order using recursion involves printing the elements of a stack starting from the bottom-most element and ending with the top-most.

In computer science, a stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. In this article, we will explore how to print the elements of a stack in reverse order using recursion. The problem statement involves designing an algorithm to print the stack elements without modifying the original stack structure.

Problem Statement:

The task is to print the elements of a given stack in reverse order while preserving the original stack. This means that after printing the elements, the stack should retain its original elements and order.

Explanation with Example:

Consider a stack with the following elements: 7, 3, 6, 1, 9, 8. The goal is to print these elements in reverse order without changing the stack itself. Using recursion, the algorithm will pop elements from the stack one by one and print them in reverse order. The output for the given stack will be: "8 9 1 6 3 7."

Pseudocode

The following pseudocode represents the algorithm to print the stack in reverse order using recursion:

procedure reverse_order(stack)
    if stack is empty
        return
    data = top element of stack
    pop the top element
    reverse_order(stack) // Recursive call
    print data
    push data back to stack

Algorithm with Explanation

  1. Begin the reverse_order procedure with the input stack.
  2. Check if the stack is empty using if stack is empty.
  3. If the stack is empty, return from the procedure, as there are no elements to process.
  4. If the stack is not empty, obtain the top element of the stack and store it in the variable data.
  5. Remove the top element from the stack using the pop operation to prepare for recursive processing.
  6. Make a recursive call to the reverse_order procedure with the updated stack (without the top element).
  7. After the recursive call, print the value stored in the variable data. This step ensures that the elements are printed in reverse order during the unwinding of recursive calls.
  8. Finally, push the value stored in data back to the stack to preserve the original stack state.

Program List

// C++ program for
// Display stack in reverse order using recursion
#include <iostream>

#include <stack>

using namespace std;
//Display stack in reverse order
void reverse_order(stack < int > & record)
{
	if (record.size() == 0)
	{
		return;
	}
	int data = record.top();
	//Remove top element 
	record.pop();
	//Recursive calling process
	reverse_order(record);
	cout << " " << data;
	//Add back to stack
	record.push(data);
}
int main()
{
	//Define a stack of integer elements
	stack < int > record;
	//Add stack elements
	record.push(7);
	record.push(3);
	record.push(6);
	record.push(1);
	record.push(9);
	record.push(8);
	cout << "\n Reverse Order Stack elements : ";
	reverse_order(record);
	return 0;
}

Output

 Reverse Order Stack elements :  7 3 6 1 9 8
// Java Program
// Display stack in reverse order using recursion
import java.util.Stack;
class MyStack
{
	public Stack < Integer > record;
	public MyStack()
	{
		record = new Stack < > ();
	}
	//Display stack elements
	public void reverse_order()
	{
		if (this.record.size() == 0)
		{
			return;
		}
		int data = this.record.peek();
		//Remove top element 
		this.record.pop();
		//Recursive calling process
		reverse_order();
		System.out.print(" " + data);
		//Add back to stack
		record.push(data);
	}
	public void add_record()
	{
		//Add stack elements
		this.record.push(7);
		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)
	{
		MyStack obj = new MyStack();
		obj.add_record();
		System.out.print("\n Reverse Order Stack elements : ");
		obj.reverse_order();
	}
}

Output

 Reverse Order Stack elements :  7 3 6 1 9 8
//Include namespace system
using System;
using System.Collections;
class MyStack
{
	public Stack record = null;
	public MyStack()
	{
		record = new Stack();
	}
	//Display stack in reverse order
	public void reverse_order()
	{
		if (this.record.Count == 0)
		{
			return;
		}
		int data = (int) this.record.Peek();
		//Remove top element 
		this.record.Pop();
		//Recursive calling process
		reverse_order();
		Console.Write(" " + data);
		//Add back to stack
		record.Push(data);
	}
	public void add_record()
	{
		//Add stack elements
		this.record.Push(7);
		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)
	{
		MyStack obj = new MyStack();
		obj.add_record();
		Console.Write("\n Reverse Order Stack elements : ");
		obj.reverse_order();
	}
}

Output

 Reverse Order Stack elements :  7 3 6 1 9 8
<?php
// Php Program
// Display stack in reverse order using recursion
class MyStack
{
    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 
        {

            array_shift($this->record);
        }
    }
    //get top element
    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 in reverse order
    public  function reverse_order()
    {
        if (count($this->record) == 0)
        {
            return;
        }
        $data = $this->peek();
        //Remove top element 
        $this->pop();
        
        //Recursive calling process
        $this->reverse_order();

        //Display stack element
        echo " ". $data;

        //Add back to stack
        $this->push($data);
    }

    public  function add_record()
    {

        //Add stack elements
        $this->push(7);
        $this->push(3);
        $this->push(6);
        $this->push(1);
        $this->push(9);
        $this->push(8);

    }
}

function main()
{
    $obj = new MyStack();
    $obj->add_record();
    echo "\n Reverse Order Stack elements : ";
    $obj->reverse_order();
    
}
main();

Output

 Reverse Order Stack elements :  7 3 6 1 9 8
// Node JS program for
// Display stack in reverse order using recursion
class MyStack
{
	constructor()
	{
		this.record = [];
	}
	//Display stack in reverse order
	reverse_order()
	{
		if (this.record.length == 0)
		{
			return;
		}
		var data = this.peek();
		//Remove top element 
		this.record.pop();
		//Recursive calling process
		this.reverse_order();
		//Display stack element
		process.stdout.write(" " + data);
		//Add back to stack
		this.record.push(data);
	}
	peek()
	{
		if (this.record.length == 0)
		{
			return;
		}
		else
		{
			return this.record[this.record.length - 1];
		}
	}
	add_record()
	{
		//Add stack elements
		this.record.push(7);
		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 MyStack();
	obj.add_record();
	process.stdout.write("\n Reverse Order Stack elements : ");
	obj.reverse_order();
}
main();

Output

 Reverse Order Stack elements :  7 3 6 1 9 8
#  Python 3 Program
#  Display stack in reverse order using recursion
class MyStack :
    def __init__(self) :
        self.record = []
    
    # Display stack in reverse order
    def reverse_order(self) :
        if (len(self.record)==0) :
            return
        
        data = self.peek()
        # Remove top element 
        self.pop()
        
        # Recursive calling process
        self.reverse_order()

        print(data, end = " ")

        # Add back to stack
        self.push(data)
    
   
    
    def add_record(self) :
        # Add stack elements
        self.push(7)
        self.push(3)
        self.push(6)
        self.push(1)
        self.push(9)
        self.push(8)
    
    def push(self,data) :
        # add element at beginning of list
        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 = MyStack()
    obj.add_record()
    print("\n Reverse Order Stack elements :", end = " ")
    obj.reverse_order()
 

if __name__ == "__main__": main()

Output

 Reverse Order Stack elements : 7 3 6 1 9 8
#  Ruby Program
#  Display stack in reverse order using recursion
class MyStack 

    # Define the accessor and reader of class MyStack  
    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 in reverse order
    def reverse_order()
    
        if (self.record.length == 0)
        
            return
        end
        data = self.peek()
        # Remove top element 
        self.pop()
     
        # Recursive calling process
        self.reverse_order()

        # Display stack element
        print(" ", data)
        # Add back to stack
        self.push(data)
    end
   
    def add_record()
    
        # Add stack elements
        self.push(7)
        self.push(3)
        self.push(6)
        self.push(1)
        self.push(9)
        self.push(8)
   
    end
end
def main()

    obj = MyStack.new()
    obj.add_record()
    print("\n Reverse Order Stack elements : ")
    obj.reverse_order()
 
end
main()

Output

 Reverse Order Stack elements :  7 3 6 1 9 8
// Scala Program
// Display stack in reverse order using recursion
import scala.collection.mutable.Stack 
class MyStack(var record: Stack[Int] )
{
	def this()
	{
		this(Stack[Int]());
	}
	//Display stack in reverse order
	def reverse_order(): Unit = {
		if (this.record.isEmpty)
		{
			return;
		}
		var data: Int = this.record.top;
		//Remove top element 
		this.record.pop();
		
		//Recursive calling process
		reverse_order();
		//Display stack element
		print(" " + data);
		//Add back to stack
		record.push(data);
	}
	
	def add_record(): Unit = {
		//Add stack elements
		this.record.push(7);
		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: MyStack = new MyStack();
		obj.add_record();
		//Before
		print("\n Reverse Order Stack elements : ");
		obj.reverse_order();
	
	}
}

Output

 Reverse Order Stack elements :  7 3 6 1 9 8

Resultant Output Explanation:

Using the provided C++ code and the algorithm, let's analyze the output for the given stack (7, 3, 6, 1, 9, 8).

The stack elements are initially printed as: 7 3 6 1 9 8 (the order in which they were added to the stack).

After applying the reverse_order algorithm, the output will be: 8 9 1 6 3 7.

Time Complexity: The time complexity of the given algorithm can be analyzed by understanding the recursive nature of the reverse_order procedure. For each element in the stack, the algorithm performs a constant amount of work (copying the top element, popping, pushing back, and printing). Therefore, the time complexity can be expressed as O(N), where N is the number of elements in the stack.

Finally

In this article, we have discussed how to print the elements of a stack in reverse order without modifying the original stack using recursion. We provided an algorithm along with pseudocode and explained it in detail. The key takeaway is that recursive functions can be effectively used to reverse the order of elements in a stack while preserving the stack's original structure. The provided C++ code successfully demonstrates the implementation of the algorithm, producing the desired output. By understanding the principles behind the algorithm, one can apply similar techniques to solve other related problems in computer science and programming.

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