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 stack in the below post.
Reverse a Stack using Recursion
The above solution requires O(n) extra space. We can reverse a stack in O(1) time if we internally represent the stack as a linked list. Reverse a stack would require a reversing of 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.
Implementation:
C++
// C++ 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 contributed 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(); } } |
Python3
# Python3 program to implement Stack # using linked list so that reverse # can be done with O(1) extra space. class StackNode: def __init__( self , data): self .data = data self . next = None class Stack: def __init__( self ): self .top = None # Push and pop operations def push( self , data): if ( self .top = = None ): self .top = StackNode(data) return s = StackNode(data) s. next = self .top self .top = s def pop( self ): s = self .top self .top = self .top. next return s # Prints contents of stack def display( self ): s = self .top while (s ! = None ): print (s.data, end = ' ' ) s = s. next # Reverses the stack using simple # linked list reversal logic. def reverse( self ): prev = self .top cur = self .top cur = cur. next succ = None prev. next = None while (cur ! = None ): succ = cur. next cur. next = prev prev = cur cur = succ self .top = prev # Driver code if __name__ = = '__main__' : s = Stack() s.push( 1 ) s.push( 2 ) s.push( 3 ) s.push( 4 ) print ( "Original Stack" ) s.display() print () # Reverse s.reverse() print ( "Reversed Stack" ) s.display() # This code is contributed by rutvik_56 |
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 |
Javascript
<script> // JavaScript program to implement Stack // using linked list so that reverse can // be done with O(1) extra space. class StackNode { constructor(data) { this .data = data; this .next = null ; } } class Stack { top = null ; // Push and pop operations push(data) { if ( this .top == null ) { this .top = new StackNode(data); return ; } var s = new StackNode(data); s.next = this .top; this .top = s; } pop() { var s = this .top; this .top = this .top.next; return s; } // Prints contents of stack display() { var s = this .top; while (s != null ) { document.write(s.data + " " ); s = s.next; } document.write( "<br>" ); } // Reverses the stack using simple // linked list reversal logic. reverse() { var 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; } } // Driver code var s = new Stack(); s.push(1); s.push(2); s.push(3); s.push(4); document.write( "Original Stack <br>" ); s.display(); // Reverse s.reverse(); document.write( "Reversed Stack <br>" ); s.display(); // This code is contributed by rdtank </script> |
Output
Original Stack 4 3 2 1 Reversed Stack 1 2 3 4
Time Complexity: O(n), as we are using a loop to traverse n times. Where n is the number of nodes in the linked list.
Auxiliary Space: O(1), as we are not using any extra space.
Contact Us