Last Updated on December 13, 2022 by Prepbytes
Problem Statement
In this problem, we are given a stack. We have to reverse the stack without using extra space in O(n).
Problem Statement Understanding
As we know, reversing a stack using recursion is the normally used technique. But here, we cannot use recursion because we have to reverse it in O(1) space. So, how can we complete the task with the given constraint?
Linked List. Yes, we can use the technique of reversing a linked list in this problem. Let us have a glance at our approach to get a clearer look.
Explanation: The given stack is reversed.
Approach
The approach is going to be pretty simple. We have to represent the stack as a linked list. By doing this, we can use the linked list reversal technique, which takes O(n) time and O(1) space. Even though the reversal will take O(n) time, push and pop operations will still take O(1) time.
Algorithm
- Create a StackNode class to represent the given stack as a linked list.
- For the push method, if the top is NULL, then create a new StackNode with the given data and put it at the top.
- Else, Create a new StackNode, say s. Now, the next of s will point to the top, and s will become the new top.
- For the pop method, create a new StackNode, say s, and it will point to the top. Now, to delete the element, the top will point to the next of the top. In the end, we will return s.
- In the reverse method, simply perform the linked list reversal logic on the given stack.
Dry Run
Code Implementation
#includeusing namespace std; class StackNode { public: int data; StackNode *next; StackNode(int data) { this->data = data; this->next = NULL; } }; class Stack { StackNode *top; public: // Push function void push(int data) { if (top == NULL) { top = new StackNode(data); return; } StackNode *s = new StackNode(data); s->next = top; top = s; } // Pop function StackNode* pop() { StackNode *s = top; top = top->next; return s; } // Function to display the element of the stack void display() { StackNode *s = top; while (s != NULL) { cout << s->data << " "; s = s->next; } cout << endl; } // Stack reversal using the 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; } }; int main() { Stack *s = new Stack(); s->push(1); s->push(3); s->push(5); s->push(7); cout << "Original Stack" << endl;; s->display(); cout << endl; s->reverse(); cout << "Reversed Stack" << endl; s->display(); return 0; }
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(3);
s.push(5);
s.push(7);
System.out.println("Original Stack");
s.display();
s.reverse();
System.out.println("Reversed Stack");
s.display();
}
}
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:
print(s.data, end = " ")
s = s.next
def reverse(self):
cur = self.top
prev = self.top
cur = cur.next
prev.next = None
while cur:
succ = cur.next
cur.next = prev
prev = cur
cur = succ
self.top = prev
s = stack()
s.push(1)
s.push(3)
s.push(5)
s.push(7)
print("Original Stack")
s.display()
s.reverse()
print("Reversed Stack")
s.display()
Output
Original Stack
7 5 3 1
Reversed Stack
1 3 5 7
[forminator_quiz id=”3584″]
Space Complexity: O(1), as only temporary variables are being created.
So, in this article, we have tried to explain the most efficient approach to reverse a stack without using extra space in O(n). As we are saving up on space in this approach, this problem becomes an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.