Reverse a Stack using Recursion in C
In this tutorial we will learn how recursion will be used in this case to reverse a stack. For loops, while loops, do-while loops, and similar constructions are not permitted. To reverse a stack, we must use recursion.
Example:
Input: x = [15, 25, 35, 45, 55]
Output: [55, 45, 35, 25, 15]
Interpretation:
The result would be [ 55, 45, 35, 25, 15] if the stack x is flipped.
Recursion can be used to reverse a stack in several different ways. The use of an auxiliary stack is the most typical method of stack reversal. All of the components will first be removed from the stack and pushed into the auxiliary stack. After every item has been pushed into the auxiliary stack, we simply print the elements that are there in reverse order. However, we won't use the auxiliary stack in this case. Recursion refers to repeatedly calling the same function, which is how we will reverse a stack.
In the recursive procedure, all the elements from the input stack are first removed, and then all the removed elements are pushed into the function call stack until the stack is empty. All of the things will be moved toward the stack once it is empty. Let's use an example to better grasp this topic.
Example:
5 <-- top
6
7
8
8 is first put at the bottom.
8 <-- top
Then, 7 is put at the bottom.
8 <-- top
7
Then, 6 is put at the bottom.
8 <-- top
7
6
Then, 5 is put at the bottom.
8 <-- top
7
6
5
Application in C Language:
// Recursive C program that reverses a stack
#include<stdio.h>
#include<stdlib.h>
#define bool int
// structure of a stack node
struct xNode
{
char val;
struct xNode *next;
};
// Declaring Function
void push ( struct xNode** top_reference,
int new_val );
int pop ( struct xNode** top_reference );
bool isEmpty ( struct xNode* top );
void print ( struct xNode* top );
// In this case, a recursive function aids in the insertion of a stack element at the bottom.
void insertAtBottom ( struct xNode** top_reference,
int item )
{
if ( isEmpty ( *top_reference ) )
push ( top_reference, item );
else
{
// Storing all items in Function Call
// When the stack is empty, the if statement is evaluated and the item is added at the bottom when isEmpty(*top ref) is true.
int temp_val = pop ( top_reference );
insertAtBottom ( top_reference, item );
// Push all the elements held in Function after the item has been inserted at the bottom.
// Calling Stack
push ( top_reference, temp_val );
}
}
// The function that uses insertAtBottom() to reverse the given stack is shown below
void reverse ( struct xNode** top_reference )
{
if ( !isEmpty ( *top_reference ) )
{
// Until we reach the end of the stack, hold all the elements in the function and call stack.
int temp_val = pop ( top_reference );
reverse ( top_reference );
// putting each item (kept in the function call stack) in sequential order from bottom to top. Each item is placed at the bottom.
insertAtBottom ( top_reference, temp_val );
}
}
// Driver Code
int main ()
{
struct xNode *x = NULL;
push ( & x, 8 );
push ( & x, 7 );
push ( & x, 6 );
push ( & x, 5 );
printf ( "\nThe given Stack is - " );
print ( x );
reverse ( & x );
printf ( "\nAnd the Reversed Stack is - " );
print(x);
return 0;
}
// Checking whether the stack is empty function
bool isEmpty ( struct xNode* top_element )
{
if ( top_element==NULL ) return 1;
else return 0;
}
// Function for inserting an item into a stack
void push ( struct xNode** top_reference,
int new_val )
{
// allocating the node into memory
struct xNode* new_node =
( struct xNode* ) malloc ( sizeof ( struct xNode ) );
if ( new_node == NULL )
{
printf ( "Stack overflow \n" );
exit ( 0 );
}
// putting in data
new_node -> val = new_val;
// Link the previous list to the new node.
new_node -> next = ( *top_reference );
// Point to the new node by moving the head.
( *top_reference ) = new_node;
}
// Function to pop an item from stack
int pop ( struct xNode** top_reference )
{
char res;
struct xNode *top_element;
// when stack is empty then it gives error
if ( *top_reference == NULL )
{
printf ( "Stack overflow \n" );
exit ( 0 );
}
else
{
top_element = *top_reference;
res = top_element->val;
*top_reference = top_element->next;
free ( top_element );
return res;
}
}
// A linked list printing function
void print ( struct xNode* top_element )
{
printf ( "\n" );
while ( top_element != NULL)
{
printf ( " %d ", top_element -> val );
top_element = top_element -> next;
}
}
Application in C++ Language:
// C++ code for reversing a
// stack using recursion
#include<bits/stdc++.h>
using namespace std;
// stack declarations
// using std::stack
stack < char > stack1;
// initialize a string to store
// result of the reversed stack
string str;
// The recursive function
// that inserts an element
// at the bottom of a stackis given below.
void insert_at_bottom ( char a )
{
if ( stack1.size () == 0 )
stack1.push ( a );
else
{
// All elements are held in Function Call
// Stack until we reach to the end of the stack
// When the stack became empty, the
// stack1.size() became zero, when the above
// part is executed and the element is
// inserted at the bottom of the stack
char b = stack1.top ();
stack1.pop ();
insert_at_bottom ( a );
// pushing all the elements held in
// Function Call Stack
// when the element is inserted
// at the bottom of the stack
stack1.push ( b );
}
}
// The function that reverses
// the given stack is shown below.
// insert_at_bottom()
void reverse ()
{
if ( stack1.size () > 0 )
{
// Holding all the elements in Function
// Call Stack until we
// reach to the end of the stack
char a = stack1.top ();
stack1.pop ();
reverse ();
// Inserting all the elements held
// in Function Call Stack
// each of them from the bottom
// to top. Every item is then
// inserted at the bottom of the stack
insert_at_bottom ( a );
}
}
// Driver Code
int main ()
{
// pushing the elements into
// the stack
stack1.push ( '5' );
stack1.push ( '6' );
stack1.push ( '7' );
stack1.push ( '8' );
cout << "The given Stack is - "<< endl;
// printing all the elements
// of the actual stack
cout << "5 " << " " << "6" << " "
<< "7" << " " << "8"
<< endl;
// function for reversing
// the stack
reverse ();
cout << " And the Reversed Stack is -"
<< endl;
// storing the values of the reversed
// stack in a string to display them
while ( ! stack1.empty () )
{
char p=stack1.top ();
stack1.pop ();
str += p;
}
//displaying the reversed stack
cout << str [ 3 ] <<" " << str [ 2 ]<<" "
<< str [ 1 ]<<" " << str [ 0 ] << endl;
return 0;
}
Output:
The given Stack is -
5 6 7 8
And the Reversed Stack is -
8 7 6 5
Time Complexity: O (n2)
Space Complexity: O (1)