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
- Begin the
reverse_order
procedure with the input stack. - Check if the stack is empty using
if stack is empty
. - If the stack is empty, return from the procedure, as there are no elements to process.
- If the stack is not empty, obtain the top element of the stack and store it in the variable
data
. - Remove the top element from the stack using the
pop
operation to prepare for recursive processing. - Make a recursive call to the
reverse_order
procedure with the updated stack (without the top element). - 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. - 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.
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.
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