Reverse a String using Stack C/C++

Reverse the given string using stack. To turn "tutorialandexample" into "elpmaxednalairotut," for instance.

Here is a straightforward stack-based technique for reversing strings.

Algorithm:

1) Make a stack that is empty.

2) Push each character in the string to the stack one at a time.

3) Remove each character from the stack one at a time, then add them back to the string.

C Program:

// A stack-based C program to reverse a given string
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>


// A stack-representing structure
struct Stack
{
	int top;
	unsigned capacity1;
	char* arr;
};


// Stack creation function with provided capacity
// It starts off with a stack size of 0.
struct Stack* createtheStack ( unsigned capacity1 )
{
	struct Stack* stack = ( struct Stack* ) malloc( sizeof( struct Stack ) );
	stack -> capacity1 = capacity1;
	stack -> top = -1;
	stack -> arr = ( char* ) malloc( stack -> capacity1 * sizeof ( char ) );
	return stack;
}


// When top equals the last index, a stack is considered full.
int isitFull ( struct Stack* stack )
{ return stack -> top == stack -> capacity1 - 1; }


// Whenever top equals -1, the stack is empty.
int isitEmpty ( struct Stack* stack )
{ return stack -> top == -1; }


// Adds a new item to the stack.
// Top is raised by 1 in the code.
void push ( struct Stack* stack, char item1 )
{
	if ( isitFull ( stack ) )
		return;
	stack -> arr [++stack -> top] = item1;
}


// Function to delete an item from the stack
// It lowers the top by one.
char pop ( struct Stack* stack )
{
	if ( isitEmpty ( stack ) )
		return INT_MIN;
	return stack -> arr [ stack->top-- ];
}


// A method that uses stacks to reverse strings
void reverse ( char str [] )
{
	// Form a stack with a size equal to the string's length.
	int no = strlen (str);
	struct Stack* stack = createtheStack (no);


	// Push the string's characters all into a stack.
	int index;
	for ( index = 0; index < no; index++ )
		push ( stack, str [ index ] );


	// Pop every character off the string and then return them to str.
	for ( index = 0; index < no; index++ )
		str [index] = pop (stack);
}


// Driver code for testing the above features
int main ()
{
	char str [] = "tutorialandexample";


	reverse (str);
	printf ( "The reversed string will be '%s'.", str );


	return 0;
}

C++ Program:

// A stack-based C++ program to reverse a given string
#include <bits/stdc++.h>
using namespace std;


// A stack-representing structure
class Stack
{
	public:
	int top;
	unsigned capacity1;
	char* arr;
};
// Stack creation function with provided capacity
// It starts off with a stack size of 0.
Stack* createtheStack ( unsigned capacity1 )
{
	Stack* stack = new Stack ();
	stack -> capacity1 = capacity1;
	stack -> top = -1;
	stack -> arr = new char [ (stack -> capacity1 * sizeof ( char ) ) ];
	return stack;
}


// When top equals the last index, a stack is considered full.
int isitFull ( Stack* stack )
{ return stack -> top == stack -> capacity1 - 1; }


// Whenever top equals -1, the stack is empty.
int isitEmpty ( Stack* stack )
{ return stack -> top == -1; }


// Adds a new item to the stack.
// Top is raised by 1 in the code.
void push ( Stack* stack, char item1 )
{
	if ( isitFull (stack) )
		return;
	stack -> arr [ ++stack -> top ] = item1;
}


// Function to delete an item from the stack
// It lowers the top by one.
char pop ( Stack* stack )
{
	if ( isitEmpty (stack) )
		return -1;
	return stack -> arr [ stack -> top-- ];
}


// A method that uses stacks to reverse string
void reverse ( char str [] )
{
	// Form a stack with a size equal to the string's length.
	int no = strlen ( str );
	Stack* stack = createtheStack (no);


	// Push the string's characters all into a stack.
	int index;
	for ( index = 0; index < no; index++ )
		push ( stack, str [index] );
	// Pop every character off the string and then return them to str.
	for ( index = 0; index < no; index++ )
		str [index] = pop (stack);
}


// Driver code for testing the above features
int main ()
{
	char str [] = "tutorialandexample";


	reverse (str);
	cout << "The reversed string will be " << str;


	return 0;
}

Output:

The reversed string will be elpmaxednalairotut

Time Complexity: O(n)

Space Complexity: O(n)

[ where n is the number of characters on the stack ]