# 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;
record.push(data);
}
int main()
{
//Define a stack of integer elements
stack < int > record;
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);
record.push(data);
}
{
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();
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);
record.Push(data);
}
{
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();
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;
}
}
//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;

\$this->push(\$data);
}

{

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

}
}

function main()
{
\$obj = new MyStack();
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);
this.record.push(data);
}
peek()
{
if (this.record.length == 0)
{
return;
}
else
{
return this.record[this.record.length - 1];
}
}
{
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();
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 = " ")

self.push(data)

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
def main() :
obj = MyStack()
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_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
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)
self.push(data)
end

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()
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);
record.push(data);
}

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

## 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.