# 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.