Tutorialspoint.dev

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

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 string in below post.

Reverse a Stack using Recursion

The above solution requires O(n) extra space. We can reverse a string in O(1) time if we internally represent the stack as a linked list. Reverse a stack would require a reversing 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.

C++

// CPP 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 contribute 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();
    }
}

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


Output:

Original Stack 
4 3 2 1
Reversed Stack 
1 2 3 4

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter