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

Reversing a stack made using the stack library from STL in C++ without using extra space isn’t possible as we will have to store the stack elements in some auxiliary space as we pop them from the stack and then push them into the stack in the reverse order. So how do we do it?

We need to find a data structure through which we can implement stacks and reverse in O(n) without using auxiliary space. One such data structure is linked lists. We can reverse a linked list in O(n) without using extra space. So all we need to do is implement stacks using a linked list and we’re good to go!

Making a Node class to implement linked list

To start off, we’ll have to make a Node class to implement a linked list. Templates help us to implement data structures of any data type. The node class will look something like this-

template <typename T>
class Node {
    public :
    T data;
    Node<T> *next;
    
    Node(T data) {
        this -> data = data;
        next = NULL;
    }
};

Count Possible Decodings of a given Digit Sequence in C++

Reversing a stack made using linked list

The next step is to make a Stack class that uses a linked list to replicate a stack. The Stack class will have all the usual functions that a stack has along with a reverse() function that prints the elements of the linked list before and after reversing. The public reverse() function calls the private rev_linkedlist() function which reverses the linked list and returns the head of the reversed linked list.

template <typename T>
class Stack {
    Node <T> *head;
    int size;
    
    private:
    Node <T>* rev_linkedlist(){
    Node <T>* current=head;
    Node <T>* next=current->next;
    Node <T>* prev=NULL;
    while(current->next!=NULL){
        current->next=prev;
        prev=current;
        current=next;
        next=next->next;
        }
    current->next=prev;
    head=current;
    return head;
    }
    
    public :
    
    Stack() {
        head=NULL;
        size=0;
    }
    
    void getSize() {
        if(size==0){
            cout<<"Stack is empty!"<<endl;
        }
        else
        cout<<"Size of the stack is "<<size<<endl;
    }
    
    bool isEmpty() {
        if(head==NULL)
            return true;
        return false;
    }
    
    void push(T element) {
        Node<T>* newnode=new Node<T>(element);
        newnode ->next=head;
        head=newnode;
        size++;
    }
    
    void pop() {
        if(head==NULL)
            cout<<"Stack is empty"<<endl;
        else{
        T a=head->data;
        Node<T> *temp=head;
        head=head->next;
        temp->next=NULL;
        delete [] temp;
        size--;
        cout<<"Element removed from the Stack is "<<a<<endl;
        }
    }
    
    void top() {
        if(head==NULL)
            cout<<"Stack is empty!"<<endl;
        else
            cout<<"Top element of the stack is "<<head->data<<endl;
    }
    void reverse(){
        Node <T>* temp1=head;
        cout<<"Stack before reversing is"<<endl;
        while(temp1!=NULL){
            cout<<temp1->data<<endl;
            temp1=temp1->next;
        }
        head=rev_linkedlist();
        Node <T>* temp2=head;
        cout<<"Stack after reversing is"<<endl;
        while(temp2!=NULL){
            cout<<temp2->data<<endl;
            temp2=temp2->next;
        }
    }
    
  
    
};

Let’s make a main() function and run our code. Make sure to add header files of your classes or put them in the same file as your main() function.

using namespace std;
#include <iostream>
#include <Stack.h>
#include <Node.h>
int main(){
    Stack<int> x;
    x.push(50);
    x.push(20);
    x.push(30);
    x.push(100);
    x.push(5);
    x.push(11);
    x.reverse();
    return 0;
}

Output

Stack before reversing is
11
5
100
30
20
50
Stack after reversing is
50
20
30
100
5
11

The output is correct and we have successfully reversed a stack without using auxiliary space in O(n) using linked list. Make sure to comment if you have any questions about this code or any suggestions regarding other codes on our website.