Given a stack st[], Reverse the stack so that the top element becomes the bottom and the bottom element becomes the top, while preserving the order of the remaining elements accordingly.
Example:
Input: st[] = [1, 2, 3, 4]
Output: [1, 2, 3, 4]
Explanation:
Input: st[] = [3, 2, 1]
Output: [3, 2, 1]
Explanation:
[Approach 1] Recursive Approach
The idea is to use the recursion to reverse the given stack.
- First, we keep removing elements from the stack until stack becomes empty.
- Once the stack is empty, we start going back in the recursion. At each step, instead of placing the element back on top, we insert it at the bottom of the stack.
- To insert an element at the bottom, we recursively pop all elements, push the current element, and then put the popped elements back.
This way we will ensuring that the element that was originally at the top moves to the bottom, and gradually the entire stack gets reversed.
C++
#include <iostream>
#include <stack>
using namespace std;
// function to insert element at the bottom of the stack
void insertAtBottom(stack<int> &st, int x) {
if (st.empty()) {
st.push(x);
return;
}
// hold the top element and remove it
int top = st.top();
st.pop();
// recursively call to reach the bottom
insertAtBottom(st, x);
st.push(top);
}
// function to reverse the stack
void reverseStack(stack<int> &st) {
if (st.empty()) return;
// hold the top element and remove it
int top = st.top();
st.pop();
// reverse the remaining stack
reverseStack(st);
// insert the held element at the bottom
insertAtBottom(st, top);
}
int main() {
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
reverseStack(st);
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
struct myStack {
int arr[MAX];
int top;
};
// function to insert element at the bottom of the stack
void insertAtBottom(struct myStack* st, int x) {
if (st->top == -1) {
st->arr[++st->top] = x;
return;
}
// hold the top element and remove it
int temp = st->arr[st->top--];
// recursively call to reach the bottom
insertAtBottom(st, x);
st->arr[++st->top] = temp;
}
// function to reverse the stack
void reverseStack(struct myStack* st) {
if (st->top == -1) return;
// hold the top element and remove it
int temp = st->arr[st->top--];
// reverse the remaining stack
reverseStack(st);
// insert the held element at the bottom
insertAtBottom(st, temp);
}
int main() {
struct myStack st;
st.top = -1;
st.arr[++st.top] = 1;
st.arr[++st.top] = 2;
st.arr[++st.top] = 3;
st.arr[++st.top] = 4;
reverseStack(&st);
while (st.top != -1) {
printf("%d ", st.arr[st.top--]);
}
return 0;
}
import java.util.Stack;
class GfG{
// function to insert element at the bottom of the stack
static void insertAtBottom(Stack<Integer> st, int x) {
if (st.isEmpty()) {
st.push(x);
return;
}
// hold the top element and remove it
int top = st.pop();
// recursively call to reach the bottom
insertAtBottom(st, x);
st.push(top);
}
// function to reverse the stack
static void reverseStack(Stack<Integer> st) {
if (st.isEmpty()) return;
// hold the top element and remove it
int top = st.pop();
// reverse the remaining stack
reverseStack(st);
// insert the held element at the bottom
insertAtBottom(st, top);
}
public static void main(String[] args) {
Stack<Integer> st = new Stack<>();
st.push(1);
st.push(2);
st.push(3);
st.push(4);
reverseStack(st);
while (!st.isEmpty()) {
System.out.print(st.pop() + " ");
}
}
}
# function to insert element at the bottom of the stack
def insertAtBottom(st, x):
if not st:
st.append(x)
return
# hold the top element and remove it
top = st.pop()
# recursively call to reach the bottom
insertAtBottom(st, x)
st.append(top)
# function to reverse the stack
def reverseStack(st):
if not st:
return
# hold the top element and remove it
top = st.pop()
# reverse the remaining stack
reverseStack(st)
# insert the held element at the bottom
insertAtBottom(st, top)
if __name__ == "__main__":
st = [1, 2, 3, 4]
reverseStack(st)
while st:
print(st.pop(), end=" ")
using System;
using System.Collections.Generic;
class GfG {
// function to insert element at the bottom of the stack
static void insertAtBottom(Stack<int> st, int x) {
if (st.Count == 0) {
st.Push(x);
return;
}
// hold the top element and remove it
int top = st.Pop();
// recursively call to reach the bottom
insertAtBottom(st, x);
st.Push(top);
}
// function to reverse the stack
static void reverseStack(Stack<int> st) {
if (st.Count == 0) return;
// hold the top element and remove it
int top = st.Pop();
// reverse the remaining stack
reverseStack(st);
// insert the held element at the bottom
insertAtBottom(st, top);
}
static void Main() {
Stack<int> st = new Stack<int>();
st.Push(1);
st.Push(2);
st.Push(3);
st.Push(4);
reverseStack(st);
while (st.Count > 0) {
Console.Write(st.Pop() + " ");
}
}
}
// function to insert element at the bottom of the stack
function insertAtBottom(st, x) {
if (st.length === 0) {
st.push(x);
return;
}
// hold the top element and remove it
let top = st.pop();
// recursively call to reach the bottom
insertAtBottom(st, x);
st.push(top);
}
// function to reverse the stack
function reverseStack(st) {
if (st.length === 0) return;
// hold the top element and remove it
let top = st.pop();
// reverse the remaining stack
reverseStack(st);
// insert the held element at the bottom
insertAtBottom(st, top);
}
// driver code
let st = [];
st.push(1);
st.push(2);
st.push(3);
st.push(4);
reverseStack(st);
let res = [];
while (st.length > 0) {
res.push(st.pop());
}
console.log(res.join(" "));
Time Complexity: O(n2)
Auxiliary Space: O(n), due to recursion stack
[Approach 2] Iterative Approach - O(n) Time and O(n) Space
We use an auxiliary stack to hold elements while popping them from the original stack. Since stacks are LIFO, pushing all elements into the auxiliary stack will naturally reverse their order. Finally, we replace the original stack with the auxiliary stack.
C++
#include <iostream>
#include <stack>
using namespace std;
void reverseStack(stack<int> &st) {
stack<int> aux;
// move all elements to auxiliary stack
while (!st.empty()) {
aux.push(st.top());
st.pop();
}
// swapping aux stack with st
swap(st, aux);
}
int main() {
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
reverseStack(st);
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// stack structure
struct myStack {
int arr[MAX];
int top;
};
// initialize stack
void init(struct myStack* st) {
st->top = -1;
}
// check empty
int isEmpty(struct myStack* st) {
return st->top == -1;
}
// push element
void push(struct myStack* st, int x) {
if (st->top == MAX - 1) return;
st->arr[++st->top] = x;
}
// pop element
int pop(struct myStack* st) {
if (isEmpty(st)) return -1;
return st->arr[st->top--];
}
// get top
int peek(struct myStack* st) {
return st->arr[st->top];
}
// function to reverse the stack
void reverseStack(struct myStack* st) {
struct myStack aux;
init(&aux);
// move all elements to auxiliary stack
while (!isEmpty(st)) {
push(&aux, pop(st));
}
// replace original stack with auxiliary
*st = aux;
}
int main() {
struct myStack st;
init(&st);
push(&st, 1);
push(&st, 2);
push(&st, 3);
push(&st, 4);
reverseStack(&st);
while (!isEmpty(&st)) {
printf("%d ", pop(&st));
}
return 0;
}
import java.util.Stack;
class GfG {
public static void reverseStack(Stack<Integer> st) {
Stack<Integer> aux = new Stack<>();
// move all elements to auxiliary stack
while (!st.isEmpty()) {
aux.push(st.pop());
}
// replace original stack with auxiliary
st.addAll(aux);
}
public static void main(String[] args) {
Stack<Integer> st = new Stack<>();
st.push(1);
st.push(2);
st.push(3);
st.push(4);
reverseStack(st);
while (!st.isEmpty()) {
System.out.print(st.pop() + " ");
}
}
}
def reverseStack(st):
aux = []
# move all elements to auxiliary stack
while st:
aux.append(st.pop())
# replace original stack with auxiliary
st[:] = aux
if __name__ == "__main__":
st = []
st.append(1)
st.append(2)
st.append(3)
st.append(4)
reverseStack(st)
while st:
print(st.pop(), end=" ")
using System;
using System.Collections.Generic;
class GfG {
static void reverseStack(ref Stack<int> st) {
Stack<int> aux = new Stack<int>();
// move all elements to auxiliary stack
while (st.Count > 0) {
aux.Push(st.Peek());
st.Pop();
}
st = aux;
}
static void Main() {
Stack<int> st = new Stack<int>();
st.Push(1);
st.Push(2);
st.Push(3);
st.Push(4);
reverseStack(ref st);
while (st.Count > 0) {
Console.Write(st.Peek() + " ");
st.Pop();
}
}
}
function reverseStack(st) {
let aux = [];
// move all elements to auxiliary stack
while (st.length > 0) {
aux.push(st.pop());
}
// replace original stack with auxiliary
st.push(...aux);
}
// Driver Code
let st = [];
st.push(1);
st.push(2);
st.push(3);
st.push(4);
reverseStack(st);
let res = [];
while (st.length > 0) {
res.push(st.pop());
}
console.log(res.join(" "));
Reverse a stack using recursion
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem