Home » Technical Interview Questions » Stack Interview Questions » Reverse a stack without using extra space in O(n)

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


Reading Time - 7 mins


Difficulty Level Easy

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.

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

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.
READ  Design a stack that supports getMin() in O(1) time and O(1) extra space

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.

READ  Find if an Expression has Duplicate Parenthesis or Not

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.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions