In this Answer, we'll learn how to change the order of elements in a given stack to reverse it. The example below demonstrates this visually.

To learn more about the Stack data structure, refer to this link.

A simple way to do this is to make a new stack and pop an element from the original stack. The popped element is pushed into the new stack, and this process is repeated until the original stack becomes empty.

However, we must make a recursive solution if we need to reverse the given stack. For this, it is helpful first to recall how recursion works.

Instead of storing the popped element in a separate, explicitly defined, and created stack, we can create a variable `temp`

to store it. A recursive solution allows separate copies of this variable to be stored. They will be stored in separate stack frames on the recursive call stack for each call of the function (the recursive call stack doesn't need to be created by us explicitly in our code, the function itself creates it).

This is illustrated below:

When the recursive calls start tracking back once the base case (stack is empty) is reached, the value of `temp`

in the function calls will be popped off the call stack. We note that inserting each `temp`

value at the bottom of our original stack during the backtracking will eventually result in a reverse stack. However, since a stack is a

We can implement another recursive function, `insertAtBottom(),`

which will be called inside the original function `reverseStack()`

. When it is time to insert `temp`

at the bottom of our stack during the backtracking of `reverseStack()`

, we can first make a call to `insertAtBottom()`

.

The visual demonstration of our solution at work is shown below:

The code below implements the `reverseStack()`

and `insertAtBottom()`

functions using an array representation of a stack.

#include <iostream>using namespace std;class Stack{int* stack_arr ;int max_size ;int current_size ;public:Stack(int max_cap){stack_arr = new int[max_cap] ;max_size = max_cap ;current_size = 0 ;}bool isEmpty(){if(current_size == 0){return 1 ;}else{return 0 ;}}void push(int element_to_push){stack_arr[current_size] = element_to_push ;current_size++ ;}int pop(){int popped = stack_arr[current_size-1];current_size-- ;return popped;}void printStack(){for(int i = current_size-1 ; i >= 0 ; i--){cout << stack_arr[i] << endl ;}cout << endl ;}int insertAtBottom(int temp) // the second recursive function{if(isEmpty()){push(temp);}else{int temp2 = pop();insertAtBottom(temp);push(temp2); // push temp2 back on original stack during backtracking}}void reverseStack() // the first recursive function{if(!isEmpty()){int temp = pop();reverseStack();insertAtBottom(temp); // insert temp at the bototm of the stack}}};int main(){int stack_size = 5 ;Stack example(stack_size);example.push(5);example.push(4);example.push(3);example.push(2);example.push(1);cout << "Original Stack:" << endl ;example.printStack();example.reverseStack();cout << "reversed Stack:" << endl ;example.printStack();return 0;}

The highlighted lines of code implement the two functions discussed, while the rest of the code is in the class definition of our stack and its main operations. These highlighted lines are explained below:

**Lines 52â€“64:**We implement the`insertAtBottom()`

function in the following steps:Pop an element from the original stack and store it in

`temp2`

.Once our original stack has been emptied, push

`temp`

onto it.During backtracking of this recursive function, push each

`temp2`

back onto our original stack.

**Lines 66â€“74:**We implement the`reverseStack()`

function in the following steps:Pop an element from the original stack and store it in a variable

`temp`

.Recursively do the same for the rest of the stack until it becomes empty. This way, the stack frame of each recursive call will contain a different value of

`temp`

.During backtracking, push each

`temp`

back onto the original stack.

Question

What is the time complexity of this solution?

Show Answer

Copyright Â©2024 Educative, Inc. All rights reserved

TRENDING TOPICS