Reverse a given stack of 'N' integers using recursion. You are required to make changes in the input parameter itself.
Note: You are not allowed to use any extra space other than the internal stack space used due to recursion.
Input: [1,2,3,4,5]
Output: [5,4,3,2,1]
The first line of input contains an integer value 'N', denoting the size of the input Stack.
The second line contains 'N' single space-separated integers, denoting the stack elements, where the leftmost integer denotes the TOP element of Stack.
'N' single space-separated integers in a single line, where the leftmost integer denotes the TOP element of the reversed stack.
3
2 1 3
3 1 2
Reverse of a give stack is 3 1 2 where first element becomes last and last becomes first.
2
3 2
2 3
0 <= N <= 10^3
Where 'N' is the number of elements in the given stack.
Time Limit: 1 sec
Use the recursion call stack to store the elements of the stack and reverse it.
We will be using two recursive methods:
Algorithm:
O(N^2), where ‘N’ is the total number of elements in the given stack.
In the worst case, reverseStack method will be called for each element in the stack( requires O(N)) time, and for each call of the reverse stack, we call InsertAtBottom which also takes O(N) time.
O(N), where ‘N’ is the total number of elements in the given stack.
In the worst case, the depth of recursion can extend up to O(N). So, extra space will be required for the recursion stack.
All tags
Sort by
Interview problems
C++ solution 100% cleared
void insertAtBottom(stack<int> &s, int element) {
if(s.empty()) {
s.push(element);
return;
}
int num = s.top();
s.pop();
insertAtBottom(s, element);
s.push(num);
}
void reverseStack(stack<int> &stack) {
if(stack.empty()) {
return;
}
int num = stack.top();
stack.pop();
reverseStack(stack);
insertAtBottom(stack, num);
}Interview problems
easy to understand
#include <stack>
using namespace std;
void insertAtBottom(stack<int> &s, int ele) {
if (s.empty()) {
s.push(ele);
} else {
int top = s.top();
s.pop();
insertAtBottom(s, ele);
s.push(top);
}
return;
}
void reverseStack(stack<int> &s) {
if (s.empty()) {
return;
}
int top = s.top();
s.pop();
reverseStack(s);
insertAtBottom(s, top);
}
Interview problems
"Reverse Stack Using Recursion" using C++
void insertSort(stack<int> &stack, int temp){
if(stack.empty()){
stack.push(temp);
return;
}
int var = stack.top();
stack.pop();
insertSort(stack, temp);
stack.push(var);
}
void reverseStack(stack<int> &stack) {
// Write your code here
if(stack.empty()) return;
int temp = stack.top();
stack.pop();
reverseStack(stack);
insertSort(stack, temp);
}
Interview problems
Using recursion
void insertBottom(stack<int> &stack, int ele){
//base case
if(stack.empty()){
stack.push(ele);
return;
}
int val = stack.top();
stack.pop();
insertBottom(stack, ele);
stack.push(val);
}
void reverseStack(stack<int> &stack) {
//base case
if(stack.empty()){
return;
}
int val = stack.top();
stack.pop();
reverseStack(stack);
insertBottom(stack, val);
}
Interview problems
easy solution
void insert_at_bottom(stack<int>&st,int ele)
{
if(st.empty())
{
st.push(ele);
return;
}
int topele=st.top();
st.pop();
insert_at_bottom(st,ele);
st.push(topele);
}
void reverseStack(stack<int>&s)
{
if(s.empty())
{
return;
}
int ele=s.top();
s.pop();
reverseStack(s);
insert_at_bottom(s,ele);
}
Interview problems
Reverse Stack Using Recursion 🔥
// Function to insert an element at the bottom of the stack 📦
void insertStack(stack<int>& stack, int x) {
// Base case: if the stack is empty, just push the element 🤔
if (stack.empty()) {
stack.push(x); // Stack: [x] 👍
return;
}
// Store the top element and pop it from the stack 💸
int num = stack.top(); // num = top element 👀
stack.pop(); // Remove the top element 🔥
// Recursive call to insert the element at the bottom 🔄
insertStack(stack, x); // Insert x at the bottom 🔩
// Push the stored top element back into the stack 💪
stack.push(num); // Stack: [..., x, num] 👍
}
// Function to reverse the stack 🔙
void reverseStack(stack<int>& stack) {
// Base case: if the stack is empty, do nothing 🙅♂️
if (stack.empty()) {
return;
}
// Store the top element and pop it from the stack 💸
int top = stack.top(); // top = top element 👀
stack.pop(); // Remove the top element 🔥
// Recursive call to reverse the remaining stack 🔄
reverseStack(stack); // Reverse the remaining stack 🔙
// Insert the stored top element at the bottom of the stack 📦
insertStack(stack, top); // Insert top at the bottom 🔩
}
// Example usage:
// Take stack: [1, 2] 📈
// 1. top = 2 👀
// then remove the 2 from the top 🔥
// and make a recursive call 🔄
// now top = 1 👀
// again remove the top 🔥
// now stack becomes empty 📦
// Now make a recursive call to insertStack to insert element 📦
// Stack: [] 📦
// Stack: [1] 👍 and return
// Again make a call and now stack: [1] 📈
// top = 1 👀
// In next iteration if Stack: [1] 🤔
// pop the top element to insert new element 🔥
// Now 1 is pop and stack becomes empty 📦
// element 2 is push into stack 🔩
// and then 1 is push into stack 👍
// Stack becomes [2, 1] 📈
Interview problems
easy soln || recursive approach || c++ soln
void solve(stack<int>& s,int x){
//base case
if(s.empty()){
s.push(x);
return ;
}
int num=s.top();
s.pop();
//recursive call
solve(s,x);
s.push(num);
}
void reverseStack(stack<int> &stack) {
//base case
if(stack.empty()){
return ;
}
int num=stack.top();
stack.pop();
//recursive call
reverseStack(stack);
solve(stack,num);
}
Interview problems
Easy java solution using extra space
import java.util.Stack;
public class Solution {
public static void reverseStack(Stack<Integer> stack) {
// write your code here
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while(!stack.isEmpty()){
stack1.push(stack.pop());
}
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
while(!stack2.isEmpty()){
stack.push(stack2.pop());
}
}
}
Interview problems
C++ Code || Using recursion
void insertAtBottom(stack<int>& stack, int x ){
// base case
if(stack.empty()){
stack.push(x);
return;
}
int num = stack.top();
stack.pop();
// recursive call
insertAtBottom(stack,x);
stack.push(num);
}
void reverseStack(stack<int> &stack) {
// base case
if(stack.empty()){
return ;
}
int num = stack.top();
stack.pop();
// recursive call
reverseStack(stack);
insertAtBottom(stack,num);
}
Interview problems
Easy Solution Using Cpp
void insertAtBottom(stack<int>& myStack, int x){
if(myStack.empty()){
myStack.push(x);
return;
}
int num = myStack.top();
myStack.pop();
insertAtBottom(myStack,x);
myStack.push(num);
}
void reverseStack(stack<int> &stack) {
if(stack.empty()){
return;
}
int num = stack.top();
stack.pop();
reverseStack(stack);
insertAtBottom(stack,num);
}
