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

Problem Statement

In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n).

Problem Statement Understanding

As we know, reversing a stack using recursion is the normally used technique. But here, we cannot use recursion because we have to reverse it in O(1) space. So, how can we complete the task with the given constraint?

Linked List. Yes, we can use the technique of reversing a linked list in this problem. Let us have a glance at our approach to get a clearer look.

Explanation: The given stack is reversed.

Approach

The approach is going to be pretty simple. We have to represent the stack as a linked list. By doing this, we can use the linked list reversal technique, which takes O(n) time and O(1) space. Even though the reversal will take O(n) time, push and pop operations will still take O(1) time.

Algorithm

  • Create a StackNode class to represent the given stack as a linked list.
  • For the push method, if the top is NULL, then create a new StackNode with the given data and put it at the top.
  • Else, Create a new StackNode, say s. Now, the next of s will point to the top, and s will become the new top.
  • For the pop method, create a new StackNode, say s, and it will point to the top. Now, to delete the element, the top will point to the next of the top. In the end, we will return s.
  • In the reverse method, simply perform the linked list reversal logic on the given stack.

Dry Run

Code Implementation

#include
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 function
    void push(int data)
    {
        if (top == NULL) {
            top = new StackNode(data);
            return;
        }
        StackNode *s = new StackNode(data);
        s->next = top;
        top = s;
    }
    //  Pop function
    StackNode* pop()
    {
        StackNode *s = top;
        top = top->next;
        return s;
    }
 
    // Function to display the element of the stack
    void display()
    {
        StackNode *s = top;
        while (s != NULL) {
            cout << s->data << " ";
            s = s->next;
        }
        cout << endl;
    }
 
    // Stack reversal using the 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;
    }
};

int main()
{
    Stack *s = new Stack();
    s->push(1);
    s->push(3);
    s->push(5);
    s->push(7);
    cout << "Original Stack" << endl;;
    s->display();
    cout << endl;
    s->reverse();
    cout << "Reversed Stack" << endl;
    s->display();
     
    return 0;
}
class StackNode {
    int data;
    StackNode next;
    public StackNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
 
class Stack {
    StackNode top;

    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;
    }

    public void display()
    {
        StackNode s = this.top;
        while (s != null) {
            System.out.print(s.data + " ");
            s = s.next;
        }
        System.out.println();
    }

    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(3);
        s.push(5);
        s.push(7);
        System.out.println("Original Stack");
        s.display();
        s.reverse();
        System.out.println("Reversed Stack");
        s.display();
    }
}

Output
Original Stack
7 5 3 1

Reversed Stack
1 3 5 7

Space Complexity: O(1), as only temporary variables are being created.

So, in this article, we have tried to explain the most efficient approach to reverse a stack without using extra space in O(n). As we are saving up on space in this approach, this problem becomes an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Can we reverse a linked list in less than O(n)?
Next post Make middle node the head in a linked list

Leave a Reply

Your email address will not be published. Required fields are marked *