C Tutorial

C Tutorial C Language Environment Setup Execution flow of C program C printf and Scanf C Data type C Token Variable in C Operators in C Comments in C Escape Sequence in C C – Storage Classes C Decision control statement Loop Statement in C Break, continue and goto statement in C Type Casting in C Function in C Recursion in C String in C C Array Pointer in C Dynamic memory allocation C –Structure Nested Structure in C Union in C File Handling in C C pre-processor Static Function In C Sizeof In C Selection Sort In C Scope Of Variables In C Runtime Vs Compile Time In C Random Access Lseek In C Queue Implementation In C Pseudo Code In C Prototype In C Pointer To Pointer In C Pointer Arithmetic In C Passing Array To Function In C Null Character In C Merge Sort In C Macros In C Library Functions In C Memory Leak In C Int In C Goto And Labels In C Fibonacci Series In C Fflush In C Derived Data Types In C Data Types In C Const Vs Volatile In C Character Set In C Character Class Tests In C Calloc In C C Pointers Arrays In C Include In C Clrscr In C C Vs Java String Literals In C Types Of Pointers In C Variables In C Volatile In C Why C Is A Middle Level Language Infix To Postfix Program In C Ceil function in C LCM of two numbers in C Quick sort in C Static in C function pointer as argument in C Top Array Keywords in C Add two numbers using the function in C Armstrong program in C using function Array, Declaring Arrays and Array Initialization Limitations of Inline Function in C Merge and Merge sort with example in C Do-While Loop in C For Loop in C While-Loop in C Difference between while and do-while loop in C Array Of Structures in C Data Structures And Algorithms in C Types Of Structures In C How to Avoid Structure Padding in C Use of Structure in C Do WHILE LOOP in C Programming Examples For Loop in C Programming Examples Entry Control Loop in C Exit control loop in C Infinite loop in C Nested loop in C pow() function in C String Handling functions in C Prime Number code in C Factorial Program in C using For Loop Factorial Program in C Using While Loop Fibonacci Series in C Using For Loop Fibonacci series in C using while loop Prime Number Program in C using for Loop While Loop in C programming examples Built-in functions in C Assert() Function C vs Java Strings Call Back Function in Embedded C Else If Ladder fgets() function Ftell() Function getc() function getch() function gets() function Heap Sort Nested if-else statement Pi() Function Positioning of file Write() function abs() function in C Attributes in C C program to find factorial of a number using Recursion Ferror() in c fopen() function in C Fibonacci series program in C using Recursion Formatted Input and output function in C Snake Game in C User Defined Functions in C Beep() function in C Cbrt() function in C Hook() function in C Isalnum() function in C C Program to find the Roots of a Quadratic Equation C Switch Statements Difference between rand() and srand() function in C Difference between while and for loop in C Doubly Linked list in C Example of Iteration in C How to use atoi() function in C How to use floor() function in C How to use sine() function in C How to use Typedef Struct in C Integer Promotions in C C Program Swap Numbers in cyclic order Using Call by Reference C Program to Find Largest Number Using Dynamic Memory Allocation C Program to Find the Largest Number using Ternary Operator C/C++ Program to Find the Size of int, float, double and char Find the Largest Three Distinct Elements in an Array using C/C++ Loop Questions in C Modulus on Negative Numbers in C Multiplication table program in C using For loop Nested Loops in C Programming Examples C Program for Mean and Median of an Unsorted Array Results of Comparison Operations in C and C++ Reverse a Stack using Recursion in C Simple hash() function in C strcat() Function in C Sum of N numbers in C using For loop Use of free() function in C Write a program that produces different results in C and C++ C Function Argument and Return Values Keywords in C Bank management system in C Calendar application in C Floor() Function in C Free() Function in C How to delete a file in C How to move a text in C Remove an element from an array in C Unformatted input() and output() function in C What are linker and loader in C

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)



ADVERTISEMENT
ADVERTISEMENT