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

Problem Statement

The problem “Reverse a stack without using extra space in O(n)” states that you are given a stack data structure. Reverse the given stack without using extra O(n) space.

Example

5 4 3 2 1

1 2 3 4 5

80 60 10 20

20 10 60 80

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

1. Create a class node containing an integer variable and a next pointer. Create a class constructor that accepts an integer as parameter. Assign the parameter value to the integer variable and set next pointer as null in the constructor.
2. After that, create class stack and initialize a pointer top of type node in it.
3. Create a function push() that accepts an integer as the parameter. Check if top is equal to null create a new node with given integer as data and store the new node in top and return.
4. Else create a new node s with given integer as data. Update next of s as top and top is equal to s.
5. Similarly, create a function pop(). Create a new node s and store the top in it. Update top as next of top and return the new node s.
6. After that, create the function reverse(). Create three nodes representing previous, current and succeeding respectively. Update the current and previous node as the top node.
7. Update current node as next of current node and the next of previous node as null.
8. While current node is not null, update the succeeding node as the next of current node, next of current node as the previos node, previous node as the current node and current node as the succeeding node.
9. Update top node as the previous node.
10. Finally create a function display() to display the reversed stack. Create a new node s and store the top in it. While s is not equal to null, print data of s and update the s as next of s.

Code

C++ Program to reverse a stack without using extra space in O(n)

#include<bits/stdc++.h> 
using namespace std; 
  
class Node { 
    public: 
        int data; 
        Node *next; 
          
        Node(int data){ 
            this->data = data; 
            this->next = NULL; 
        } 
}; 
  
class Stack{ 
      
    Node *top; 
      
    public: 
      
        void push(int data){ 
            if (top == NULL) { 
                top = new Node(data); 
                return; 
            } 
            Node *s = new Node(data); 
            s->next = top; 
            top = s; 
        } 
          
        Node* pop(){ 
            Node *s = top; 
            top = top->next; 
            return s; 
        } 
      
        void display(){ 
            Node *s = top; 
            while (s != NULL) { 
                cout << s->data << " "; 
                s = s->next; 
            } 
            cout << endl; 
        } 
      
        void reverse(){ 
            Node *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; 
        } 
}; 
  
int main(){ 
    Stack *s = new Stack(); 
    
    s->push(1); 
    s->push(2); 
    s->push(3); 
    s->push(4);
    s->push(5);
    
    s->reverse(); 
  
    s->display(); 
      
    return 0; 
}

1 2 3 4 5

Java Program to reverse a stack without using extra space in O(n)

class Node{ 
    int data; 
    Node next; 
    
    public Node(int data){ 
        this.data = data; 
        this.next = null; 
    } 
} 
  
class Stack{ 
    Node top; 
  
    public void push(int data){ 
        if (this.top == null){ 
            top = new Node(data); 
            return; 
        } 
        
        Node s = new Node(data); 
        s.next = this.top; 
        this.top = s; 
    } 
    
    public Node pop(){ 
        Node s = this.top; 
        this.top = this.top.next; 
        return s; 
    } 
  
    public void display(){ 
        Node s = this.top; 
        
        while (s != null){ 
            System.out.print(s.data + " "); 
            s = s.next; 
        } 
        
    } 
  
    public void reverse(){
        
        Node 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; 
    } 
} 
  
class reverseStack{ 
    
    public static void main(String[] args){ 
        
        Stack s = new Stack(); 
        
        s.push(1); 
        s.push(2); 
        s.push(3); 
        s.push(4);
        s.push(5);
        
        s.reverse(); 
  
        s.display(); 
    } 
}

1 2 3 4 5

Complexity Analysis

Time Complexity

O(n) where n is the number of elements in the data structure stack. Since we have used a single loop to run over the elements of the stack. The time complexity is linear.

Space Complexity

O(1) because we are using constant extra space. Since the space taken for storing the input will not be counted for the algorithm. Thus the space complexity is constant. But the program as a whole requires linear space complexity.