# Stack | Set 3 (Reverse a string using stack)

Given a string, reverse it using stack. For example “GeeksQuiz” should be converted to “ziuQskeeG”.

Following is simple algorithm to reverse a string using stack.

```1) Create an empty stack.
2) One by one push all characters of string to stack.
3) One by one pop all characters from stack and put
them back to string.```

Following programs implements above algorithm.

## C++

 `// CPP program to reverse a string using stack  ` `#include ` `using` `namespace` `std; ` ` `  `// A structure to represent a stack  ` `class` `Stack  ` `{  ` `    ``public``: ` `    ``int` `top;  ` `    ``unsigned capacity;  ` `    ``char``* array;  ` `};  ` ` `  `// function to create a stack of given  ` `// capacity. It initializes size of stack as 0  ` `Stack* createStack(unsigned capacity)  ` `{  ` `    ``Stack* stack = ``new` `Stack(); ` `    ``stack->capacity = capacity;  ` `    ``stack->top = -1;  ` `    ``stack->array = ``new` `char``[(stack->capacity * ``sizeof``(``char``))];  ` `    ``return` `stack;  ` `}  ` ` `  `// Stack is full when top is equal to the last index  ` `int` `isFull(Stack* stack)  ` `{ ``return` `stack->top == stack->capacity - 1; }  ` ` `  `// Stack is empty when top is equal to -1  ` `int` `isEmpty(Stack* stack)  ` `{ ``return` `stack->top == -1; }  ` ` `  `// Function to add an item to stack.  ` `// It increases top by 1  ` `void` `push(Stack* stack, ``char` `item)  ` `{  ` `    ``if` `(isFull(stack))  ` `        ``return``;  ` `    ``stack->array[++stack->top] = item;  ` `}  ` ` `  `// Function to remove an item from stack.  ` `// It decreases top by 1  ` `char` `pop(Stack* stack)  ` `{  ` `    ``if` `(isEmpty(stack))  ` `        ``return` `-1;  ` `    ``return` `stack->array[stack->top--];  ` `}  ` ` `  `// A stack based function to reverese a string  ` `void` `reverse(``char` `str[])  ` `{  ` `    ``// Create a stack of capacity  ` `    ``//equal to length of string  ` `    ``int` `n = ``strlen``(str);  ` `    ``Stack* stack = createStack(n);  ` ` `  `    ``// Push all characters of string to stack  ` `    ``int` `i;  ` `    ``for` `(i = 0; i < n; i++)  ` `        ``push(stack, str[i]);  ` ` `  `    ``// Pop all characters of string and  ` `    ``// put them back to str  ` `    ``for` `(i = 0; i < n; i++)  ` `        ``str[i] = pop(stack);  ` `}  ` ` `  `// Driver code  ` `int` `main()  ` `{  ` `    ``char` `str[] = ``"GeeksQuiz"``;  ` ` `  `    ``reverse(str);  ` `    ``cout << ``"Reversed string is "` `<< str;  ` ` `  `    ``return` `0;  ` `}  ` ` `  `// This code is contributed by rathbhupendra `

## C

 `// C program to reverse a string using stack ` `#include ` `#include ` `#include ` `#include ` ` `  `// A structure to represent a stack ` `struct` `Stack ` `{ ` `    ``int` `top; ` `    ``unsigned capacity; ` `    ``char``* array; ` `}; ` ` `  `// function to create a stack of given  ` `// capacity. It initializes size of stack as 0 ` `struct` `Stack* createStack(unsigned capacity) ` `{ ` `    ``struct` `Stack* stack = (``struct` `Stack*) ``malloc``(``sizeof``(``struct` `Stack)); ` `    ``stack->capacity = capacity; ` `    ``stack->top = -1; ` `    ``stack->array = (``char``*) ``malloc``(stack->capacity * ``sizeof``(``char``)); ` `    ``return` `stack; ` `} ` ` `  `// Stack is full when top is equal to the last index ` `int` `isFull(``struct` `Stack* stack) ` `{ ``return` `stack->top == stack->capacity - 1; } ` ` `  `// Stack is empty when top is equal to -1 ` `int` `isEmpty(``struct` `Stack* stack) ` `{ ``return` `stack->top == -1; } ` ` `  `// Function to add an item to stack.  ` `// It increases top by 1 ` `void` `push(``struct` `Stack* stack, ``char` `item) ` `{ ` `    ``if` `(isFull(stack)) ` `        ``return``; ` `    ``stack->array[++stack->top] = item; ` `} ` ` `  `// Function to remove an item from stack.  ` `// It decreases top by 1 ` `char` `pop(``struct` `Stack* stack) ` `{ ` `    ``if` `(isEmpty(stack)) ` `        ``return` `INT_MIN; ` `    ``return` `stack->array[stack->top--]; ` `} ` ` `  `// A stack based function to reverese a string ` `void` `reverse(``char` `str[]) ` `{ ` `    ``// Create a stack of capacity  ` `    ``//equal to length of string ` `    ``int` `n = ``strlen``(str); ` `    ``struct` `Stack* stack = createStack(n); ` ` `  `    ``// Push all characters of string to stack ` `    ``int` `i; ` `    ``for` `(i = 0; i < n; i++) ` `        ``push(stack, str[i]); ` ` `  `    ``// Pop all characters of string and  ` `    ``// put them back to str ` `    ``for` `(i = 0; i < n; i++) ` `        ``str[i] = pop(stack); ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``char` `str[] = ``"GeeksQuiz"``; ` ` `  `    ``reverse(str); ` `    ``printf``(``"Reversed string is %s"``, str); ` ` `  `    ``return` `0; ` `} `

## Java

 `/* Java program to reverse  ` `String using Stack */` `     `  `import` `java.util.*; ` ` `  `//stack ` `class` `Stack ` `{ ` `    ``int` `size; ` `    ``int` `top; ` `    ``char``[] a;  ` ` `  `    ``//function to check if stack is empty ` `    ``boolean` `isEmpty() ` `    ``{ ` `        ``return` `(top < ``0``); ` `    ``} ` `     `  `    ``Stack(``int` `n) ` `    ``{ ` `        ``top = -``1``; ` `        ``size = n; ` `        ``a = ``new` `char``[size]; ` `    ``} ` ` `  `    ``//function to push element in Stack ` `    ``boolean` `push(``char` `x) ` `    ``{ ` `        ``if` `(top >= size) ` `        ``{ ` `        ``System.out.println(``"Stack Overflow"``); ` `        ``return` `false``; ` `        ``} ` `        ``else` `        ``{ ` `            ``a[++top] = x; ` `            ``return` `true``; ` `        ``} ` `    ``} ` ` `  `    ``//function to pop element from stack ` `    ``char` `pop() ` `    ``{ ` `        ``if` `(top < ``0``) ` `        ``{ ` `        ``System.out.println(``"Stack Underflow"``); ` `        ``return` `0``; ` `        ``} ` `        ``else` `        ``{ ` `            ``char` `x = a[top--]; ` `            ``return` `x; ` `        ``} ` `    ``} ` `} ` ` `  ` `  `// Driver code ` `class` `Main ` `{ ` `    ``//function to reverse the string ` `    ``public` `static` `void` `reverse(StringBuffer str) ` `    ``{ ` `        ``// Create a stack of capacity  ` `        ``// equal to length of string ` `        ``int` `n = str.length(); ` `        ``Stack obj = ``new` `Stack(n); ` `         `  `        ``// Push all characters of string  ` `        ``// to stack ` `        ``int` `i; ` `        ``for` `(i = ``0``; i < n; i++) ` `        ``obj.push(str.charAt(i)); ` `     `  `        ``// Pop all characters of string  ` `        ``// and put them back to str ` `        ``for` `(i = ``0``; i < n; i++) ` `        ``{  ` `            ``char` `ch = obj.pop(); ` `            ``str.setCharAt(i,ch); ` `        ``} ` `    ``}  ` `     `  `    ``//driver function ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``//create a new string ` `        ``StringBuffer s= ``new` `StringBuffer(``"GeeksQuiz"``); ` `         `  `        ``//call reverse method ` `        ``reverse(s); ` `         `  `        ``//print the reversed string ` `        ``System.out.println(``"Reversed string is "` `+ s); ` `    ``} ` `} `

## Python

 `# Python program to reverse a string using stack ` ` `  `# Function to create an empty stack.  ` `# It initializes size of stack as 0 ` `def` `createStack(): ` `    ``stack``=``[] ` `    ``return` `stack ` ` `  `# Function to determine the size of the stack ` `def` `size(stack): ` `    ``return` `len``(stack) ` ` `  `# Stack is empty if the size is 0 ` `def` `isEmpty(stack): ` `    ``if` `size(stack) ``=``=` `0``: ` `        ``return` `true ` ` `  `# Function to add an item to stack .  ` `# It increases size by 1  ` `def` `push(stack,item): ` `    ``stack.append(item) ` ` `  `#Function to remove an item from stack.  ` `# It decreases size by 1 ` `def` `pop(stack): ` `    ``if` `isEmpty(stack): ``return` `    ``return` `stack.pop() ` ` `  `# A stack based function to reverse a string ` `def` `reverse(string): ` `    ``n ``=` `len``(string) ` `     `  `    ``# Create a empty stack ` `    ``stack ``=` `createStack() ` ` `  `    ``# Push all characters of string to stack ` `    ``for` `i ``in` `range``(``0``,n,``1``): ` `        ``push(stack,string[i]) ` ` `  `    ``# Making the string empty since all  ` `    ``#characters are saved in stack  ` `    ``string``=``"" ` ` `  `    ``# Pop all characters of string and  ` `    ``# put them back to string ` `    ``for` `i ``in` `range``(``0``,n,``1``): ` `        ``string``+``=``pop(stack) ` `         `  `    ``return` `string ` `     `  `# Driver program to test above functions ` `string``=``"GeeksQuiz"` `string ``=` `reverse(string) ` `print``(``"Reversed string is "` `+` `string) ` ` `  `# This code is contributed by Sunny Karira `

Output:

`Reversed string is ziuQskeeG`

Time Complexity:
O(n) where n is number of characters in stack.
Auxiliary Space: O(n) for stack.

A string can also be reversed without using any auxiliary space. Following C, Java, C# and Python programs to implement reverse without using stack.

## C++

 `// C++ program to reverse a string without using stack  ` `#include ` `using` `namespace` `std; ` ` `  `// A utility function to swap two characters  ` `void` `swap(``char` `*a, ``char` `*b)  ` `{  ` `    ``char` `temp = *a;  ` `    ``*a = *b;  ` `    ``*b = temp;  ` `}  ` ` `  `// A stack based function to reverese a string  ` `void` `reverse(``char` `str[])  ` `{  ` `    ``// get size of string  ` `    ``int` `n = ``strlen``(str), i;  ` ` `  `    ``for` `(i = 0; i < n/2; i++)  ` `        ``swap(&str[i], &str[n-i-1]);  ` `}  ` ` `  `// Driver program to test above functions  ` `int` `main()  ` `{  ` `    ``char` `str[] = ``"abc"``;  ` ` `  `    ``reverse(str);  ` `    ``cout<<``"Reversed string is "``<< str;  ` ` `  `    ``return` `0;  ` `}  ` ` `  `//This is code is contributed by rathbhupendra `

## C

 `// C program to reverse a string without using stack ` `#include ` `#include ` ` `  `// A utility function to swap two characters ` `void` `swap(``char` `*a, ``char` `*b) ` `{ ` `    ``char` `temp = *a; ` `    ``*a = *b; ` `    ``*b = temp; ` `} ` ` `  `// A stack based function to reverese a string ` `void` `reverse(``char` `str[]) ` `{ ` `    ``// get size of string ` `    ``int` `n = ``strlen``(str), i; ` ` `  `    ``for` `(i = 0; i < n/2; i++) ` `        ``swap(&str[i], &str[n-i-1]); ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``char` `str[] = ``"abc"``; ` ` `  `    ``reverse(str); ` `    ``printf``(``"Reversed string is %s"``, str); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to reverse a string without using stack  ` `public` `class` `GFG { ` `// A utility function to swap two characters  ` ` `  `    ``static` `void` `swap(``char` `a[], ``int` `index1, ``int` `index2) { ` `        ``char` `temp = a[index1]; ` `        ``a[index1] = a[index2]; ` `        ``a[index2] = temp; ` `    ``} ` ` `  `// A stack based function to reverese a string  ` `    ``static` `void` `reverse(``char` `str[]) { ` `        ``// get size of string  ` `        ``int` `n = str.length, i; ` ` `  `        ``for` `(i = ``0``; i < n / ``2``; i++) { ` `            ``swap(str, i, n - i - ``1``); ` `        ``} ` `    ``} ` ` `  `// Driver program to test above functions  ` `    ``public` `static` `void` `main(String[] args) { ` `        ``char` `str[] = ``"abc"``.toCharArray(); ` ` `  `        ``reverse(str); ` `        ``System.out.printf(``"Reversed string is "` `+ String.valueOf(str)); ` `    ``} ` `} ` `// This code is contributed by 29AjayKumar `

## Python

 `# Python program to reverse a string without stack ` ` `  `# Function to reverse a string ` `def` `reverse(string): ` `    ``string ``=` `string[::``-``1``] ` `    ``return` `string ` ` `  `# Driver program to test above functions ` `string ``=` `"abc"` `string ``=` `reverse(string) ` `print``(``"Reversed string is "` `+` `string) ` ` `  `# This code is contributed by Sunny Karira `

## C#

 `// C# program to reverse a string without using stack  ` `using` `System; ` `public` `class` `GFG {  ` `// A utility function to swap two characters  ` ` `  `    ``static` `void` `swap(``char` `[]a, ``int` `index1, ``int` `index2) {  ` `        ``char` `temp = a[index1];  ` `        ``a[index1] = a[index2];  ` `        ``a[index2] = temp;  ` `    ``}  ` ` `  `// A stack based function to reverese a string  ` `    ``static` `void` `reverse(``char` `[]str) {  ` `        ``// get size of string  ` `        ``int` `n = str.Length, i;  ` ` `  `        ``for` `(i = 0; i < n / 2; i++) {  ` `            ``swap(str, i, n - i - 1);  ` `        ``}  ` `    ``}  ` ` `  `// Driver program to test above functions  ` `    ``public` `static` `void` `Main() {  ` `        ``char` `[]str = ``"abc"``.ToCharArray();  ` ` `  `        ``reverse(str);  ` `        ``Console.WriteLine(``"Reversed string is "` `+ String.Join(``""``,str));  ` `    ``}  ` `}  ` `// This code is contributed by PrinciRaj1992 `

Output:

`Reversed string is cba`

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

Stack Stack

code

load comments