How to clone a stack without using extra space in Python
Hello coders, in this tutorial we will be learning how to clone a stack without using and extra space in Python.
The aim of this program is to clone the Original stack to the Duplicate Stack without wasting any other space, side by side we have to keep in mind that the order should always be maintained.
Clone a stack in Python without using extra space
The optimal approach for this problem should be, first of all, reverse the original stack and pop the elements one by one from the original stack, and at the same time start pushing it in the duplicate stack.
Let’s have a look at the algorithm for this problem:
- Initialize class Stack.
- Declare push, pop, and display function.
- Define a Reverse function to reverse the original stack without using extra space.
- Pop elements from the original stack and store it in temp variable.
- Push temp variable in the duplicate stack.
- Repeat steps 4 and 5 until the length of the original stack is zero.
- Display duplicate stack.
class StackNode(object): def __init__(self, data): self.data = data self.next = None class Stack(object): def __init__(self): self.top = None def push(self, value): newVal = StackNode(value) if self.top == None: self.top = newVal else: newVal.next = self.top self.top = newVal def pop(self): val = self.top.data self.top = self.top.next return val def display(self): current = self.top while current != None: print(current.data) current = current.next print() def reverse(self): current, temp, prev = self.top, None, None while current != None: temp = current.next current.next = prev prev = current current = temp self.top = prev def isEmpty(self): return self.top == None original = Stack() duplicate = Stack() original.push('A') original.push('B') original.push('C') print("Original Stack:") original.display() original.reverse() while original.isEmpty() != True: duplicate.push(original.pop()) print("Duplicate Stack:") duplicate.display()
Original Stack: C B A Duplicate Stack: C B A
The time complexity of the above program is O(n).
In the nutshell, hope you have understood the problem easily.