Reverse a stack without using extra space in O(n)

Last Updated : 10 Jan, 2023

Reverse a Stack without using recursion and extra space. Even the functional Stack is not allowed.

Examples:

Input : 1->2->3->4
Output : 4->3->2->1

Input :  6->5->4
Output : 4->5->6

We have discussed a way of reversing a stack in the below post.
Reverse a Stack using Recursion

The above solution requires O(n) extra space. We can reverse a stack in O(1) time if we internally represent the stack as a linked list. Reverse a stack would require a reversing of a linked list which can be done with O(n) time and O(1) extra space.
Note that push() and pop() operations still take O(1) time.

Implementation:

C++

// C++ program to implement Stack  
// using linked list so that reverse 
// can be done with O(1) extra space. 
#include<bits/stdc++.h> 
using namespace std; 
  
class StackNode { 
    public: 
    int data; 
    StackNode *next; 
      
    StackNode(int data) 
    { 
        this->data = data; 
        this->next = NULL; 
    } 
}; 
  
class Stack { 
      
    StackNode *top; 
      
    public: 
      
    // Push and pop operations 
    void push(int data) 
    { 
        if (top == NULL) { 
            top = new StackNode(data); 
            return; 
        } 
        StackNode *s = new StackNode(data); 
        s->next = top; 
        top = s; 
    } 
      
    StackNode* pop() 
    { 
        StackNode *s = top; 
        top = top->next; 
        return s; 
    } 
  
    // prints contents of stack 
    void display() 
    { 
        StackNode *s = top; 
        while (s != NULL) { 
            cout << s->data << " "; 
            s = s->next; 
        } 
        cout << endl; 
    } 
  
    // Reverses the stack using simple 
    // linked list reversal logic. 
    void reverse() 
    { 
        StackNode *prev, *cur, *succ; 
        cur = prev = top; 
        cur = cur->next; 
        prev->next = NULL; 
        while (cur != NULL) { 
  
            succ = cur->next; 
            cur->next = prev; 
            prev = cur; 
            cur = succ; 
        } 
        top = prev; 
    } 
}; 
  
// driver code 
int main() 
{ 
    Stack *s = new Stack(); 
    s->push(1); 
    s->push(2); 
    s->push(3); 
    s->push(4); 
    cout << "Original Stack" << endl;; 
    s->display(); 
    cout << endl; 
      
    // reverse 
    s->reverse(); 
  
    cout << "Reversed Stack" << endl; 
    s->display(); 
      
    return 0; 
} 
// This code is contributed by Chhavi. 

Java

// Java program to implement Stack using linked 
// list so that reverse can be done with O(1)  
// extra space. 
class StackNode { 
    int data; 
    StackNode next; 
    public StackNode(int data) 
    { 
        this.data = data; 
        this.next = null; 
    } 
} 
  
class Stack { 
    StackNode top; 
  
    // Push and pop operations 
    public void push(int data) 
    { 
        if (this.top == null) { 
            top = new StackNode(data); 
            return; 
        } 
        StackNode s = new StackNode(data); 
        s.next = this.top; 
        this.top = s; 
    } 
    public StackNode pop() 
    { 
        StackNode s = this.top; 
        this.top = this.top.next; 
        return s; 
    } 
  
    // prints contents of stack 
    public void display() 
    { 
        StackNode s = this.top; 
        while (s != null) { 
            System.out.print(s.data + " "); 
            s = s.next; 
        } 
        System.out.println(); 
    } 
  
    // Reverses the stack using simple 
    // linked list reversal logic. 
    public void reverse() 
    { 
        StackNode prev, cur, succ; 
        cur = prev = this.top; 
        cur = cur.next; 
        prev.next = null; 
        while (cur != null) { 
  
            succ = cur.next; 
            cur.next = prev; 
            prev = cur; 
            cur = succ; 
        } 
        this.top = prev; 
    } 
} 
  
public class reverseStackWithoutSpace { 
    public static void main(String[] args) 
    { 
        Stack s = new Stack(); 
        s.push(1); 
        s.push(2); 
        s.push(3); 
        s.push(4); 
        System.out.println("Original Stack"); 
        s.display(); 
  
        // reverse 
        s.reverse(); 
  
        System.out.println("Reversed Stack"); 
        s.display(); 
    } 
} 

Python3

# Python3 program to implement Stack  
# using linked list so that reverse 
# can be done with O(1) extra space. 
class StackNode: 
      
    def __init__(self, data): 
          
        self.data = data 
        self.next = None
  
class Stack: 
      
    def __init__(self): 
           
        self.top = None
       
    # Push and pop operations 
    def push(self, data): 
      
        if (self.top == None): 
            self.top = StackNode(data) 
            return
          
        s = StackNode(data) 
        s.next = self.top 
        self.top = s 
       
    def pop(self): 
      
        s = self.top 
        self.top = self.top.next
        return s 
   
    # Prints contents of stack 
    def display(self): 
      
        s = self.top 
          
        while (s != None): 
            print(s.data, end = ' ') 
            s = s.next
          
    # Reverses the stack using simple 
    # linked list reversal logic. 
    def reverse(self): 
  
        prev = self.top 
        cur = self.top 
        cur = cur.next
        succ = None
        prev.next = None
          
        while (cur != None): 
            succ = cur.next
            cur.next = prev 
            prev = cur 
            cur = succ 
          
        self.top = prev 
      
# Driver code 
if __name__=='__main__': 
      
    s = Stack() 
    s.push(1) 
    s.push(2) 
    s.push(3) 
    s.push(4) 
      
    print("Original Stack") 
    s.display() 
    print() 
       
    # Reverse 
    s.reverse() 
   
    print("Reversed Stack") 
    s.display() 
       
# This code is contributed by rutvik_56

C#

// C# program to implement Stack using linked 
// list so that reverse can be done with O(1)  
// extra space. 
using System;  
  
public class StackNode 
{ 
    public int data; 
    public StackNode next; 
    public StackNode(int data) 
    { 
        this.data = data; 
        this.next = null; 
    } 
} 
  
public class Stack  
{ 
    public StackNode top; 
  
    // Push and pop operations 
    public void push(int data) 
    { 
        if (this.top == null) 
        { 
            top = new StackNode(data); 
            return; 
        } 
        StackNode s = new StackNode(data); 
        s.next = this.top; 
        this.top = s; 
    } 
      
    public StackNode pop() 
    { 
        StackNode s = this.top; 
        this.top = this.top.next; 
        return s; 
    } 
  
    // prints contents of stack 
    public void display() 
    { 
        StackNode s = this.top; 
        while (s != null)  
        { 
            Console.Write(s.data + " "); 
            s = s.next; 
        } 
        Console.WriteLine(); 
    } 
  
    // Reverses the stack using simple 
    // linked list reversal logic. 
    public void reverse() 
    { 
        StackNode prev, cur, succ; 
        cur = prev = this.top; 
        cur = cur.next; 
        prev.next = null; 
        while (cur != null) 
        { 
            succ = cur.next; 
            cur.next = prev; 
            prev = cur; 
            cur = succ; 
        } 
        this.top = prev; 
    } 
} 
  
public class reverseStackWithoutSpace  
{ 
    // Driver code 
    public static void Main(String []args) 
    { 
        Stack s = new Stack(); 
        s.push(1); 
        s.push(2); 
        s.push(3); 
        s.push(4); 
        Console.WriteLine("Original Stack"); 
        s.display(); 
  
        // reverse 
        s.reverse(); 
  
        Console.WriteLine("Reversed Stack"); 
        s.display(); 
    } 
} 
  
// This code is contributed by Arnab Kundu 

Javascript

<script> 
  
// JavaScript program to implement Stack  
// using linked list so that reverse can  
// be done with O(1) extra space. 
class StackNode  
{ 
    constructor(data)  
    { 
        this.data = data; 
        this.next = null; 
    } 
} 
  
class Stack  
{ 
    top = null; 
      
    // Push and pop operations 
    push(data) 
    { 
        if (this.top == null)  
        { 
            this.top = new StackNode(data); 
            return; 
        } 
        var s = new StackNode(data); 
        s.next = this.top; 
        this.top = s; 
    } 
      
    pop()  
    { 
        var s = this.top; 
        this.top = this.top.next; 
        return s; 
    } 
      
    // Prints contents of stack 
    display()  
    { 
        var s = this.top; 
        while (s != null) 
        { 
            document.write(s.data + " "); 
            s = s.next; 
        } 
        document.write("<br>"); 
    } 
      
    // Reverses the stack using simple 
    // linked list reversal logic. 
    reverse()  
    { 
        var prev, cur, succ; 
        cur = prev = this.top; 
        cur = cur.next; 
        prev.next = null; 
          
        while (cur != null)  
        { 
            succ = cur.next; 
            cur.next = prev; 
            prev = cur; 
            cur = succ; 
        } 
        this.top = prev; 
    } 
} 
  
// Driver code 
var s = new Stack(); 
s.push(1); 
s.push(2); 
s.push(3); 
s.push(4); 
document.write("Original Stack <br>"); 
s.display(); 
  
// Reverse 
s.reverse(); 
  
document.write("Reversed Stack <br>"); 
s.display(); 
  
// This code is contributed by rdtank 
  
</script>

Output

Original Stack
4 3 2 1 

Reversed Stack
1 2 3 4

Time Complexity: O(n), as we are using a loop to traverse n times. Where n is the number of nodes in the linked list.
Auxiliary Space: O(1), as we are not using any extra space.

GeeksforGeeks

Improve

Sort a stack using a temporary stack

Delete middle element of a stack

Stack implementation in different language

Some questions related to Stack implementation

Easy problems on Stack

Intermediate problems on Stack

Hard problems on Stack

Reverse a stack without using extra space in O(n)

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?