Clonar una pila sin espacio adicional

Dada una pila de origen, copie el contenido de la pila de origen a la pila de destino manteniendo el mismo orden sin usar espacio adicional.
Ejemplos: 

Input : Source:- |3|
                 |2|
                 |1|

Output : Destination:- |3|
                       |2|
                       |1|

Input : Source:- |a|
                 |b|
                 |c|

Output : Destination:- |a|
                       |b|
                       |c|

Enfoque: para resolver esto sin usar espacio adicional, primero invertimos la pila de origen, luego extraemos los elementos superiores de la pila de origen uno por uno y los empujamos hacia la pila de destino. Seguimos los siguientes pasos para invertir la pila de origen: 
 

1. Inicialice una cuenta variable a 0.
2. Extraiga el elemento superior de la pila de origen y guárdelo en la variable topVal .
3. Ahora extraiga los elementos de la pila de origen y empújelos a la pila de destino hasta que la longitud de la pila de origen sea igual a count .
4. Empuje topVal en la pila de origen y luego extraiga todos los elementos en la pila de destino y empújelos a la pila de origen.
5. Incrementa el valor de count .
6. Si el recuento no es igual a la longitud de la pila de origen: 1, repita el proceso desde el paso 2.

A continuación se muestra la implementación del enfoque anterior:

# Python3 program to copy the contents from source stack
# into destination stack without using extra space
  
# Define a class for Stack
class Stack(object):
      
    def __init__(self):
        self.stack = []
          
    def push(self, value):
        self.stack.append(value)
          
    def pop(self):
        return self.stack.pop()
          
    def length(self):
        return len(self.stack)
          
    def display(self):
        for i in range(len(self.stack)-1, -1, -1):
            print(self.stack[i])
              
        print()
          
source = Stack()     # Source Stack
dest = Stack()         # Destination Stack
  
source.push(1)
source.push(2)
source.push(3)
  
print("Source Stack:")
source.display()
  
count = 0
  
# Reverse the order of the values in source stack
while count != source.length() - 1:
      
    topVal = source.pop()
    while count != source.length():
        dest.push(source.pop())
          
    source.push(topVal)
    while dest.length() != 0:
        source.push(dest.pop())
          
    count += 1
  
# Pop the values from source and push into destination stack
while source.length() != 0:
    dest.push(source.pop())
      
print("Destination Stack:")
dest.display()

Producción: 
 

Source Stack:
3
2
1

Destination Stack:
3
2
1

Complejidad temporal:  O(n ² )

Espacio auxiliar: O(n)
Enfoque eficiente: un mejor enfoque sería representar la pila como una lista enlazada. Invierta la pila de origen de la misma manera que invertimos una lista vinculada, extraiga los elementos superiores de la pila de origen uno por uno y empújelos a la pila de destino.
A continuación se muestra la implementación del enfoque anterior:
 

# Python3 program to copy the contents from source stack
# into destination stack without using extra space 
# in linear time using Linked List
  
class StackNode(object):
      
    def __init__(self, data):
        self.data = data
        self.next = None
  
# Class for Stack to represent it as Linked list
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
          
source = Stack()        # Source Stack
dest = Stack()          # Destination Stack
  
source.push(1)
source.push(2)
source.push(3)
  
print("Source Stack:")
source.display()
  
source.reverse()
  
# Pop the values from source and push into destination stack
while source.isEmpty() != True:
    dest.push(source.pop())
      
print("Destination Stack:")
dest.display()

Producción: 

Source Stack:
3
2
1

Destination Stack:
3
2
1

Complejidad de tiempo:  O(n)

Espacio Auxiliar: O(n)