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 are C and Python programs that implements above algorithm.
Python Programming:
# 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.
[ad type=”banner”]
A string can also be reversed without using any auxiliary space. Following C and Python programs to implement reverse without using stack.
Python Programming:
# 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
Output:
Reversed string is cba
[ad type=”banner”]