Aula 6, exercício 5 c - como inverter elementos de uma pilha usando pilhas auxiliares

Question

Show how to use the transfer function, described in Exercise R-6.3, and two temporary stacks, to replace the contents of a given stack S with those same elements, but in reversed order.

O exercício pede para criar uma função que remova e recoloque todos os elementos de uma pilha S, em ordem inversa à ordem original, usando duas pilhas temporárias.

Answer 1

Existe uma biblioteca do python chamada Queue, que tem uma classe chamada LifoQueue, que é uma pilha, sendo que Lifo é a sigla em inglês para Last In, First Out, ou seja, a definição de uma pilha. Vou importar essa biblioteca.

 import Queue

S = Queue.LifoQueue (maxsize=0)
#criei uma pilha chamada S, sem limite de tamanho. Nesta classe, 
#se vc estabelece o tamanho como zero o tamanho não estaá limitado.

S.put(1)
S.put(2)
S.put(3)

AUX1=Queue.LifoQueue(maxsize=0)
AUX2=Queue.LifoQueue(maxsize=0)
#criei as duas pilhas auxiliares


#preciso criar um erro que identifique se a lista de destino não é 
#vazia originalmente, porque caso haja algum elemento nela, o 
#resultado não será a lista original invertida
class erro1(Exception):
    """Erro: lista de destino não vazia originalmente"""
    pass

def transfer(stack1,stack2):
    '''
    função que se destina a transferir os conteúdos de uma pilha, 
    stack1, para outra pilha, stack2, invertendo a ordem dos seus 
    conteúdos
        inputs: 
            stack1: pilha com n elementos da classe LifoQueue
            stack2: pilha vazia
        outputs:
            stack1: pilha vazia
            stack2: pilha com n elementos da classe LifoQueue, 
                   sendo esses elementos os elementos invertidos 
                   do input stack1
    '''
    if stack2.empty()==True:
        if stack1.empty()==True:
            #duas pilhas estão vazias, então uma já é a 
            #outra com elementos invertidos
            return stack1,stack2
        else:
            while stack1.empty()==False:
                stack2.put(stack1.get())
            return stack1,stack2
    else:
        raise erro1('pilha de destino não vazia')

#Se quiser testar se a função de transferência funcionou, 
#descomente e rode para ver se os elementos de S são 
#repassados para AUX1 de forma invertida
#S,AUX1=transfer(S,AUX1)
#S.empty()
#AUX1.empty()
#print (AUX1.get())
#print (AUX1.get())
#print (AUX1.get())
#Sim, funcionou. O S ficou vazio e o AUX1 ficou com 
#os elementos ao contrário. Lembre-se de redefinir S.

#Agora vamos implementar uma solução em que os 
#elementos terminem no próprio S.

def transferfullcircle(stack1,stack2,stack3):
    '''
    função que se destina a transferir os elementos de uma pilha 
     para si mesma, em ordem inversa, usando duas pilhas auxliares
        inputs:
            stack1: pilha com n elementos da classe LifoQueue
            stack2: pilha vazia da classe LifoQueue
            stack3: pilha vazia da classe LifoQueue
        outputs: 
            stack1: pilha com n elementos da classe LifoQueue, 
             em ordem inversa
            stack2: pilha vazia da classe LifoQueue
            stack3: pilha vazia da classe LifoQueue
    '''
    if (stack2.empty()==True & stack3.empty()==True):
            if stack1.empty()==True:
            #se a pilha1 está vazia, então seus elementos 
            #já estão em ordem inversa.
                return stack1
            else:
                stack1,stack2=transfer(stack1,stack2)
                stack2,stack3=transfer(stack2,stack3)
                stack3,stack1=transfer(stack3,stack1)
                return stack1,stack2,stack3
    else:
        raise erro1('pilha de destino não vazia')


#Imprimir elementos de S original#
print ('S original:')
print (S.get())
print (S.get())
print (S.get())     

S.put(1)
S.put(2)
S.put(3)

#aplicar a função de transfeência total
S,AUX1,AUX2=transferfullcircle(S,AUX1,AUX2)

#imprimir elementos de S invertidos
print('S invertido:')
print (S.get())
print (S.get())
print (S.get())