Reverse a stack without using extra space in O(n)
Last Updated :
10 Jan, 2023
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.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...