Reversing a Stack with the help of another empty Stack
Last Updated :
30 Nov, 2023
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:
1
2
3
4
5
Explanation:
Input Stack:
5
4
3
2
1
Reversed Stack:
1
2
3
4
5
Input: stack = {1, 3, 5, 4, 2}
Output:
1
3
5
4
2
Approach 1: Follow the steps below to solve the problem:
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>
using namespace std;
void transfer(stack< int >& s1,
stack< int >& s2, int n)
{
for ( int i = 0; i < n; i++) {
int temp = s1.top();
s1.pop();
s2.push(temp);
}
}
void reverse_stack_by_using_extra_stack(stack< int >& s,
int n)
{
stack< int > s2;
for ( int i = 0; i < n; i++) {
int x = s.top();
s.pop();
transfer(s, s2, n - i - 1);
s.push(x);
transfer(s2, s, n - i - 1);
}
}
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
import java.io.*;
import java.util.*;
class GFG{
static void transfer(Stack<Integer> s1,
Stack<Integer> s2, int n)
{
for ( int i = 0 ; i < n; i++)
{
int temp = s1.peek();
s1.pop();
s2.push(temp);
}
}
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++)
{
int x = s.peek();
s.pop();
transfer(s, s2, n - i - 1 );
s.push(x);
transfer(s2, s, n - i - 1 );
}
}
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();
}
}
}
|
Python3
def transfer(s1, s2, n):
for i in range (n):
temp = s1[ - 1 ]
s1.pop()
s2.append(temp)
def reverse_stack_by_using_extra_stack(s, n):
s2 = []
for i in range (n):
x = s[ - 1 ]
s.pop()
transfer(s, s2, n - i - 1 )
s.append(x)
transfer(s2, s, n - i - 1 )
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()
|
C#
using System;
using System.Collections.Generic;
class GFG{
static void transfer(Stack< int > s1,
Stack< int > s2, int n)
{
for ( int i = 0; i < n; i++) {
int temp = s1.Peek();
s1.Pop();
s2.Push(temp);
}
}
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++) {
int x = s.Peek();
s.Pop();
transfer(s, s2, n - i - 1);
s.Push(x);
transfer(s2, s, n - i - 1);
}
}
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();
}
}
}
|
Javascript
<script>
function transfer(s1, s2, n)
{
for (i = 0; i < n; i++) {
var temp = s1[s1.length-1];
s1.pop();
s2.push(temp);
}
}
function reverse_stack_by_using_extra_stack(s,n)
{
var s2 = [];
var i;
for (i = 0; i < n; i++) {
var x = s[s.length-1];
s.pop();
transfer(s, s2, n - i - 1);
s.push(x);
transfer(s2, s, n - i - 1);
}
}
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>
|
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;
}
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
def reverse_stack_by_using_extra_stack(s, n):
ans = []
for i in range (n):
ans.append(s.pop())
return ans
if __name__ = = "__main__" :
n = 5
s = []
s.append( 1 )
s.append( 2 )
s.append( 3 )
s.append( 4 )
s.append( 5 )
s = reverse_stack_by_using_extra_stack(s, n)
for i in range (n):
print (s[ - 1 ], end = " " )
s.pop()
|
C#
using System;
using System.Collections.Generic;
class Program
{
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;
}
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);
Stack< int > reversedStack = ReverseStackUsingExtraStack(s, n);
for ( int i = 0; i < n; i++)
{
Console.Write(reversedStack.Peek() + " " );
reversedStack.Pop();
}
}
}
|
Javascript
<script>
function reverseStackByUsingExtraStack(stack, n) {
let reversedStack = [];
for (let i = 0; i < n; i++) {
reversedStack.push(stack.pop());
}
return reversedStack;
}
let n = 5;
let stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack = reverseStackByUsingExtraStack(stack, n);
for (let i = 0; i < n; i++) {
console.log(stack[stack.length - 1]);
stack.pop();
}
}
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(N)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...