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++
#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:
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;
}
void display()
{
StackNode *s = top;
while (s != NULL) {
cout << s->data << " ";
s = s->next;
}
cout << endl;
}
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(2);
s->push(3);
s->push(4);
cout << "Original Stack" << endl;;
s->display();
cout << endl;
s->reverse();
cout << "Reversed Stack" << endl;
s->display();
return 0;
}
|
Java
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(2);
s.push(3);
s.push(4);
System.out.println("Original Stack");
s.display();
s.reverse();
System.out.println("Reversed Stack");
s.display();
}
}
|
Python3
class StackNode:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
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
def display(self):
s = self.top
while (s != None):
print(s.data, end = ' ')
s = s.next
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
if __name__=='__main__':
s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
print("Original Stack")
s.display()
print()
s.reverse()
print("Reversed Stack")
s.display()
|
C#
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;
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)
{
Console.Write(s.data + " ");
s = s.next;
}
Console.WriteLine();
}
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);
Console.WriteLine("Original Stack");
s.display();
s.reverse();
Console.WriteLine("Reversed Stack");
s.display();
}
}
|
Javascript
<script>
class StackNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class Stack
{
top = null;
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;
}
display()
{
var s = this.top;
while (s != null)
{
document.write(s.data + " ");
s = s.next;
}
document.write("<br>");
}
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;
}
}
var s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
document.write("Original Stack <br>");
s.display();
s.reverse();
document.write("Reversed Stack <br>");
s.display();
</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.
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!