Program to Reverse a String using a Stack Data Structure in C++ and Python

Strings:

A string data type is used in most computer languages for data values that are made up of ordered sequences of characters, such as “hello world.” A string can include any visible or unseen series of characters, and characters can be repeated. The length of a string is the number of characters in it, and “hello world” has length 11 – made up of 10 letters and 1 space. The maximum length of a string is usually restricted. There is also the concept of an empty string, which includes no characters and has a length of zero.

A string can be both a constant and a variable. If it is a constant, it is commonly expressed as a string of characters surrounded by single or double quotes.

Stack:

Stacking objects means putting them on top of one another in the English language. This data structure allocates memory in the same manner.

Data structures are essential for organizing storage in computers so that humans can access and edit data efficiently. Stacks were among the first data structures to be defined in computer science. In layman’s terms, a stack is a linear accumulation of items. It is a collection of objects that provides fast last-in, first-out (LIFO) insertion and deletion semantics. It is a modern computer programming and CPU architecture array or list structure of function calls and parameters. Elements in a stack are added or withdrawn from the top of the stack in a “last in, first out” order, similar to a stack of dishes at a restaurant.

Unlike lists or arrays, the objects in the stack do not allow for random access.

Given a string the task is to reverse the given string using stack data structure in C++ and python.

Examples:

Example1:

Input:

given string ="hellothisisBTechGeeks"

Output:

Printing the given string before reversing : hellothisisBTechGeeks
Printing the given string after reversing : skeeGhceTBsisihtolleh

Example2:

Input:

given string ="skyisbluieIFC"

Output:

Printing the given string before reversing : skyisbluieIFC
Printing the given string after reversing : CFIeiulbsiyks

Example3:

Input:

given string="cirusfinklestein123"

Output:

Printing the given string before reversing : cirusfinklestein123
Printing the given string after reversing : 321nietselknifsuric

Program to Reverse a String using a Stack Data Structure in C++ and Python

Drive into Python Programming Examples and explore more instances related to python concepts so that you can become proficient in generating programs in Python Programming Language.

1)Reversing the string using stack<> function in C++

It is critical to concentrate on the algorithm in order to develop better code. This could be the initial step in selecting a problem; one must consider the optimal algorithm before moving on to the implementation and coding.

The following steps may be useful:

  • Scan the given string or given string as static input
  • The first step would be to start with an empty stack.
  • In C++, we use stack<type>, where type is the data type of the stack (like integer, character, string, etc).
  • Then, using the push function, add the characters from the string one by one to the stack, so that the last character in the string is at the top.
  • Consider a for loop that runs a certain string length number of times.
  • Using the pop() function, pop the character and replace the popped characters in the given string.
  • Print the string

Below is the implementation:

#include <bits/stdc++.h>
using namespace std;
// function which reverses the given string using stack
void revString(string& givenstr)
{
    // Taking a empty stack of character type
    stack<char> st;

    // Traversing the given string using for loop
    for (char character : givenstr) {
        // adding each element of the given string to stack
        st.push(character);
    }

    // popping all elements from the stack and
    // replacing the elements of string with the popped
    // element
    for (int i = 0; i < givenstr.length(); i++) {
        // intializing the ith character of string with the
        // top element of the stack
        givenstr[i] = st.top();
        // popping the top element from the stack using
        // pop() function
        st.pop();
    }
}

int main()
{
    // given string
    string givenstr = "hellothisisBTechGeeks";
    // printing the string before reversing elements
    cout << "Printing the given string before reversing : "
         << givenstr << endl;
    revString(givenstr);
    cout << "Printing the given string after reversing : "
         << givenstr << endl;

    return 0;
}

Output:

Printing the given string before reversing : hellothisisBTechGeeks
Printing the given string after reversing : skeeGhceTBsisihtolleh

All the characters present in the string get reversed using the above approach(including space characters).

2)Reversing the string using deque in Python

We use deque to copy all elements from the givenstring(which performs the same operation as a stack in this case)

We use the join method to join all the characters of the given string after reversing.

Below is the implementation:

from collections import deque
# given string
givenstr = "HellothisisBTechGeeks"
# Printing the given string before reversing
print("Printing the given string before reversing : ")
print(givenstr)
# creating the stack from the given string
st = deque(givenstr)

# pop all characters from the stack and join them back into a string
givenstr = ''.join(st.pop() for _ in range(len(givenstr)))

# Printing the given string after reversing
print("Printing the given string after reversing : ")
print(givenstr)

Output:

Printing the given string before reversing : 
HellothisisBTechGeeks
Printing the given string after reversing : 
skeeGhceTBsisihtolleH

Related Programs: