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:

Algorithm

1. Initialize class Stack.
2. Declare push, pop, and display function.
3. Define a Reverse function to reverse the original stack without using extra space.
4. Pop elements from the original stack and store it in temp variable.
5. Push temp variable in the duplicate stack.
6. Repeat steps 4 and 5 until the length of the original stack is zero.
7. Display duplicate stack.

Source Code

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() 

Output

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.