Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++

How to reverse a string using stack in c++

Abhilash

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Problem Statement

Given a string, reverse the string in place, so it does not create a new string. Instead, it modifies the original string.

Example 1:

  • Input: str = "hi-educative"
  • Output: "evitacude-ih"

Example 2:

  • Input: str = "hi-answer!!!"
  • Output: '!!!rewsna-ih'

Algorithm

In this algorithm, we’ll use a stack data structure to reverse the string.

A Stack is a linear data structure in which the element inserted last is the element to be deleted first.

The algorithm contains the following steps:

  1. Create an empty stack.
  2. Push all the characters of the string into the stack.
  3. One by one, pop each character from the stack until the stack is empty.
  4. Place the popped characters back into the string from the zeroth position.
  • Time Complexity - O(N)
  • Space Complexity - O(N)

Here, we’ll use the STL implementation of stack in c++. Refer How to use the STL stack in C++ to learn more.

Demo

Let’s look at the demo below:

Reverse a string using stack
1 of 10

Code example

Let’s look at the code below:

#include <iostream>
#include <stack>
#include <string>
using namespace std;
void reverseString(string &str) {
stack<int> stk;
for (char ch: str) stk.push(ch);
for (int i = 0; i < str.length(); i++) {
str[i] = stk.top();
stk.pop();
}
}
int main() {
string str = "hi-educative";
cout << "Original String - " << str << endl;
reverseString(str);
cout << "Reversed String - " << str;
}
Reverse a string using stack

Code explanation

  • Lines 7 to 16: We define a method called reverseString() that accepts a string and reverses it.
  • Line 8 We define a stack.
  • Line 10: Each character of the string is pushed onto the stack.
  • Lines 12 to 15: Each character is popped from the stack and put into the string, starting from the 0th index.
  • Line 19: We define the str string.
  • Line 20: We print the original string with no modifications.
  • Line 21: We invoke the reverseString() method with the parameter as str.
  • Line 22: We print the modified/reversed string.

RELATED TAGS

c++

CONTRIBUTOR

Abhilash
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring