Open In App

Reversing a Stack with the help of another empty Stack

Last Updated : 30 Nov, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given a Stack consisting of N elements, the task is to reverse the Stack using an extra stack.

Examples:

Input: stack = {1, 2, 3, 4, 5} 
Output: 





Explanation: 
Input Stack: 





Reversed Stack: 




5

Input: stack = {1, 3, 5, 4, 2} 
Output: 




2

Approach 1: Follow the steps below to solve the problem:

Below is the implementation of the above approach.

C++




// C++ program to reverse a stack
// by using an extra stack
#include <bits/stdc++.h>
using namespace std;
 
// Function to transfer elements of
// the stack s1 to the stack s2
void transfer(stack<int>& s1,
              stack<int>& s2, int n)
{
    for (int i = 0; i < n; i++) {
 
        // Store the top element
        // in a temporary variable
        int temp = s1.top();
 
        // Pop out of the stack
        s1.pop();
 
        // Push it into s2
        s2.push(temp);
    }
}
 
// Function to reverse a stack using another stack
void reverse_stack_by_using_extra_stack(stack<int>& s,
                                        int n)
{
    stack<int> s2;
 
    for (int i = 0; i < n; i++) {
 
        // Store the top element
        // of the given stack
        int x = s.top();
 
        // Pop that element
        // out of the stack
        s.pop();
 
        transfer(s, s2, n - i - 1);
        s.push(x);
        transfer(s2, s, n - i - 1);
    }
}
 
// Driver Code
int main()
{
    int n = 5;
 
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
 
    reverse_stack_by_using_extra_stack(s, n);
 
    for (int i = 0; i < n; i++) {
        cout << s.top() << " ";
        s.pop();
    }
    return 0;
}


Java




// Java program to reverse a stack
// by using an extra stack
import java.io.*;
import java.util.*;
 
class GFG{
   
// Function to transfer elements of
// the stack s1 to the stack s2
static void transfer(Stack<Integer> s1,
                     Stack<Integer> s2, int n)
{
    for(int i = 0; i < n; i++)
    {
         
        // Store the top element
        // in a temporary variable
        int temp = s1.peek();
 
        // Pop out of the stack
        s1.pop();
 
        // Push it into s2
        s2.push(temp);
    }
}
 
// Function to reverse a stack using another stack
static void reverse_stack_by_using_extra_stack(Stack<Integer> s,
                                               int n)
{
    Stack<Integer> s2 = new Stack<Integer>();
 
    for(int i = 0; i < n; i++)
    {
         
        // Store the top element
        // of the given stack
        int x = s.peek();
 
        // Pop that element
        // out of the stack
        s.pop();
 
        transfer(s, s2, n - i - 1);
        s.push(x);
        transfer(s2, s, n - i - 1);
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 5;
 
    Stack<Integer> s = new Stack<Integer>();
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
 
    reverse_stack_by_using_extra_stack(s, n);
 
    for(int i = 0; i < n; i++)
    {
        System.out.print(s.peek() + " ");
        s.pop();
    }
}
}
 
// This code is contributed by Dharanendra L V.


Python3




# Python3 program to reverse a stack
# by using an extra stack
 
# Function to transfer elements of
# the stack s1 to the stack s2
def transfer(s1, s2, n):
     
    for i in range(n):
 
        # Store the top element
        # in a temporary variable
        temp = s1[-1]
 
        # Pop out of the stack
        s1.pop()
 
        # Push it into s2
        s2.append(temp)
 
# Function to reverse a stack using another stack
def reverse_stack_by_using_extra_stack(s, n):
 
    s2 = []
     
    for i in range(n):
 
        # Store the top element
        # of the given stack
        x = s[-1]
 
        # Pop that element
        # out of the stack
        s.pop()
 
        transfer(s, s2, n - i - 1)
        s.append(x)
        transfer(s2, s, n - i - 1)
 
# Driver Code
if __name__ == "__main__":
 
    n = 5
 
    s = []
    s.append(1)
    s.append(2)
    s.append(3)
    s.append(4)
    s.append(5)
 
    reverse_stack_by_using_extra_stack(s, n)
 
    for i in range(n):
        print(s[-1], end = " ")
        s.pop()
         
# This code is contributed by ukasp


C#




// C# program to reverse a stack
// by using an extra stack
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to transfer elements of
// the stack s1 to the stack s2
static void transfer(Stack<int> s1,
              Stack<int> s2, int n)
{
    for (int i = 0; i < n; i++) {
 
        // Store the top element
        // in a temporary variable
        int temp = s1.Peek();
 
        // Pop out of the stack
        s1.Pop();
 
        // Push it into s2
        s2.Push(temp);
    }
}
 
// Function to reverse a stack using another stack
static void reverse_stack_by_using_extra_stack(Stack<int> s,
                                        int n)
{
    Stack<int> s2 = new Stack<int>();
 
 
    for (int i = 0; i < n; i++) {
 
        // Store the top element
        // of the given stack
        int x = s.Peek();
 
        // Pop that element
        // out of the stack
        s.Pop();
 
        transfer(s, s2, n - i - 1);
        s.Push(x);
        transfer(s2, s, n - i - 1);
    }
}
 
// Driver Code
public static void Main()
{
    int n = 5;
 
    Stack<int> s = new Stack<int>();
 
    s.Push(1);
    s.Push(2);
    s.Push(3);
    s.Push(4);
    s.Push(5);
 
    reverse_stack_by_using_extra_stack(s, n);
 
    for (int i = 0; i < n; i++) {
        Console.Write(s.Peek() + " ");
        s.Pop();
    }
}
}
 
// This code is contributed by SURENDRA_GANGWAR.


Javascript




<script>
 
// JavaScript program to reverse a stack
// by using an extra stack
 
// Function to transfer elements of
// the stack s1 to the stack s2
function transfer(s1, s2, n)
{
    for (i = 0; i < n; i++) {
 
        // Store the top element
        // in a temporary variable
        var temp = s1[s1.length-1];
 
        // Pop out of the stack
        s1.pop();
 
        // Push it into s2
        s2.push(temp);
    }
}
 
// Function to reverse a stack using another stack
function reverse_stack_by_using_extra_stack(s,n)
{
    var s2 = [];
    var i;
    for (i = 0; i < n; i++) {
 
        // Store the top element
        // of the given stack
        var x = s[s.length-1];
 
        // Pop that element
        // out of the stack
        s.pop();
 
        transfer(s, s2, n - i - 1);
        s.push(x);
        transfer(s2, s, n - i - 1);
    }
}
 
// Driver Code
    var n = 5;
 
    var s = []
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
 
    reverse_stack_by_using_extra_stack(s, n);
    var i;
    for (i = 0; i < n; i++) {
        document.write(s[s.length-1] + ' ');
        s.pop();
    }
 
</script>


Output

1 2 3 4 5





Time Complexity: O(N2
Auxiliary Space: O(N)

 Approach 2: Follow the steps below to solve the problem:

  • Initialize an empty stack called ans.
  • Pop the top element of the given stack S and push it into the stack ans.
  • Return the stack ans, which will contain the reversed elements of the stack S.

Below is the implementation of the above approach.

C++




#include<bits/stdc++.h>
using namespace std;
 
stack<int> reverse_stack_by_using_extra_stack(stack<int> s, int n){
    stack<int> ans;
    for(int i = 0; i < n; i++){
        ans.push(s.top());
        s.pop();
    }
    return ans;
}
// Nikunj Sonigara
int main()
{
    int n = 5;
  
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
  
    s = reverse_stack_by_using_extra_stack(s, n);
  
    for (int i = 0; i < n; i++) {
        cout << s.top() << " ";
        s.pop();
    }
    return 0;
}


Java




import java.util.Stack;
 
class GFG {
    static Stack<Integer> reverseStackByUsingExtraStack(Stack<Integer> s, int n) {
        Stack<Integer> ans = new Stack<>();
        for (int i = 0; i < n; i++) {
            ans.push(s.pop());
        }
        return ans;
    }
 
    public static void main(String[] args) {
        int n = 5;
  
        Stack<Integer> s = new Stack<>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        s.push(5);
  
        s = reverseStackByUsingExtraStack(s, n);
  
        for (int i = 0; i < n; i++) {
            System.out.print(s.peek() + " ");
            s.pop();
        }
    }
}


Python3




# Define a function to reverse a stack using an extra stack
def reverse_stack_by_using_extra_stack(s, n):
    ans = []
    for i in range(n):
        ans.append(s.pop())
    return ans
 
# Main function
if __name__ == "__main__":
    n = 5
 
    # Create a stack and push elements into it
    s = []
    s.append(1)
    s.append(2)
    s.append(3)
    s.append(4)
    s.append(5)
 
    # Reverse the stack using the function
    s = reverse_stack_by_using_extra_stack(s, n)
 
    # Print the reversed stack
    for i in range(n):
        print(s[-1], end=" ")
        s.pop()


C#




using System;
using System.Collections.Generic;
 
class Program
{
    // Define a function to reverse a stack using an extra stack
    static Stack<int> ReverseStackUsingExtraStack(Stack<int> s, int n)
    {
        Stack<int> reversedStack = new Stack<int>();
        for (int i = 0; i < n; i++)
        {
            reversedStack.Push(s.Pop());
        }
        return reversedStack;
    }
 
    // Main function
    static void Main()
    {
        int n = 5;
 
        // Create a stack and push elements into it
        Stack<int> s = new Stack<int>();
        s.Push(1);
        s.Push(2);
        s.Push(3);
        s.Push(4);
        s.Push(5);
 
        // Reverse the stack using the function
        Stack<int> reversedStack = ReverseStackUsingExtraStack(s, n);
 
        // Print the reversed stack
        for (int i = 0; i < n; i++)
        {
            Console.Write(reversedStack.Peek() + " ");
            reversedStack.Pop();
        }
    }
}
 
// This code is contributed by shivamgupta0987654321


Javascript




<script>
 
// Define a function to reverse a stack using an extra stack
function reverseStackByUsingExtraStack(stack, n) {
    let reversedStack = [];
    for (let i = 0; i < n; i++) {
        reversedStack.push(stack.pop());
    }
    return reversedStack;
}
 
// Main function
    let n = 5;
 
    // Create a stack and push elements into it
    let stack = [];
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
 
    // Reverse the stack using the function
    stack = reverseStackByUsingExtraStack(stack, n);
 
    // Print the reversed stack
    for (let i = 0; i < n; i++) {
        console.log(stack[stack.length - 1]);
        stack.pop();
    }
}
 
 
</script>


Output

1 2 3 4 5 





Time Complexity: O(N) 
Auxiliary Space: O(N)



Like Article
Suggest improvement
Previous
Next
Share your thoughts in the comments

Similar Reads