Kevin’s stack problem
Kevin has recently learned the concept of “STACK”. During his practice, he got stuck in a problem where he has to reverse a string ‘S’ using a stack. So, he appoints you to help him in reversing the string ‘S’. All you have to do is to find the reversed string.

Please reverse the string using a stack so that Kevin gets to know where he is getting wrong after seeing your solution. It is guaranteed that strings will only be composed of English alphabets.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case will contain a string ‘S’.

Output Format:

For each test case, return the reversed string. Output for every test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Kevin’s stack problem

Kevin has recently learned the concept of “STACK”. During his practice, he got stuck in a problem where he has to reverse a string ‘S’ using a stack. So, he appoints you to help him in reversing the string ‘S’. All you have to do is to find the reversed string.

Please reverse the string using a stack so that Kevin gets to know where he is getting wrong after seeing your solution. It is guaranteed that strings will only be composed of English alphabets.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a string ‘S’.

Output Format:

For each test case, return the reversed string.

Output for every test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= |S| <= 10^4

Time limit: 1 sec

Accepted Answer

Using a Stack

The basic idea is to push the whole string into a stack (character by character) and then take off each character from the stack one by one. The steps are as follows:

Iterate through ‘S’.
- Push each character into the stack.
Keep removing the top character from the stack until the stack becomes empty. Append each drawn character to the new string.
Return the new string.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the given string ‘S’.

We are using a stack to store each string’s character, so the space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the given string ‘S’.

Since we are iterating through the string once, so the time complexity will be O(N). Push and pop functions take constant time in the case of the stack. Thus, the overall time complexity is O(N).

Java (SE 1.8)

/*
	Time complexity: O(N) 
	Space complexity: O(N)
	
	Where 'N' is the length of the given string 'S'.
*/

import java.util.Stack;

public class Solution {
	public static String kevinStackProblem(String s) {

		// Make a stack.
		Stack st = new Stack();

		// Iterate over the string and put each character into the stack.
		for (int i = 0; i < s.length(); i++) {
			st.push(s.charAt(i));
		}

		// To store the reversed string.
		StringBuilder ans = new StringBuilder();

		// Remove all characters from the stack and appends in the answer string.
		while (!st.empty()) {
			char x = st.peek();
			ans.append(x);
			st.pop();
		}

		// Return the ans string.
		return ans.toString();
	}
}

C++ (g++ 5.4)

/*

	Time complexity: O(N) 

	Space complexity: O(N)

	

	Where ‘N’ is the length of the given string ‘S’.

*/



string kevinStackProblem(string &s)

{   

    // Make a stack.

    stack st;



    // Iterate over the string and puts each character into the stack.

    for (int i = 0; i < s.length(); i++)

    {

        st.push(s[i]);

    }



    // Make a answer string.

    string ans = "";



    // Remove all characters from the stack and appends in the answer string.

    while (!st.empty())

    {

        char x = st.top();

        ans.push_back(x);

        st.pop();

    }



    // Return the ans string.

    return ans;

}

Python (3.5)

'''
	Time complexity: O(N) 
	Space complexity: O(N)
	
	Where ‘N’ is the length of the given string ‘S’.
'''

from collections import deque

def kevinStackProblem(givenString):
    
    s = ""
    stack = deque()
    for st in givenString:
        stack.append(st)
        
    while len(stack) > 0:
        s += stack.pop()
        
    return s