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

Answer 2

Muito interessante sua implementação, Maria Carolina! Achei muito útil este módulo que você utilizou.

Para replicar o seu cálculo precisei trocar o início do código de "import Queue" para "import queue as Queue" para que código funcionasse.

Apesar de não fazer parte do enunciado da pergunta, acho interessante sempre comparar o tempo de execução de um algoritmo com uma alternativa. Implementei algo muito simples para ilustrar como fazer esta comparação, exportando o conteúdo da pilha para uma lista, usando a função .reverse() e exportando novamente para outra pilha. Consegui com esta implementação um tempo de execução cerca de 40% menor que a sua, o que sugere ainda haver espaço para otimização de seu código.

O código utilizado para a função alternativa e o cômputo do tempo de execução foi o seguinte:

def transferfullcircle_usandolista(stack1):
    #Cria uma função similar à transferfullcircle, mas 
    #usando uma lista e a função .reverse() ao invés de usar
    #duas pilhas auxiliares.
    stack2=Queue.LifoQueue(maxsize=0)
    n=stack1.qsize() #Tamanho da lista
    x=list()
    for i in range(0,n):
        x.append(stack1.get())
    x.reverse()
    for i in range(0,n):
      stack2.put(x[i]) 
    return stack2

#Teste da função transferfullcircle_usandolista
#p1= Queue.LifoQueue (maxsize=0)
#p1.put(1)
#p1.put(2)
#p1.put(3)
#p2=transferfullcircle_usandolista(p1)
#print(p2.get())
#print(p2.get())
#print(p2.get())

#Teste de velocidade de transferfullcircle vs transferfullcircle_usandolista
def transferfullcircle_testedevelocidade():
  #Primeiro cria a pilha com 1000 elementos
  S=Queue.LifoQueue (maxsize=0)
  for i in range(1000):
     S.put(i)
  #Agora executa a função transferfullcircle
  AUX1=Queue.LifoQueue(maxsize=0)
  AUX2=Queue.LifoQueue(maxsize=0)
  S,AUX1,AUX2=transferfullcircle(S,AUX1,AUX2)
  return 0
def transferfullcircle_usandolista_testedevelocidade():
  #Primeiro cria a pilha com 1000 elementos
  S=Queue.LifoQueue (maxsize=0)
  for i in range(1000):
     S.put(i)
  #Agora executa a função transferfullcircle_usandolista
  S=transferfullcircle_usandolista(S)
  return 0
import timeit
tempo1=timeit.timeit('transferfullcircle_testedevelocidade()', number=1000, setup="from __main__ import transferfullcircle_testedevelocidade")
tempo2=timeit.timeit('transferfullcircle_usandolista_testedevelocidade()', number=1000, setup="from __main__ import transferfullcircle_usandolista_testedevelocidade")
print("Tempo (em segundos) de execução de transferfullcircle de uma pilha de 1000 elementos, calculada 1000 vezes:")
print(tempo1)
print("Tempo (em segundos) de execução de transferfullcircle_usandolista de uma pilha de 1000 elementos, calculada 1000 vezes:")
print(tempo2)
print("Razão entre tempos:")
print(tempo2/tempo1)

E o output da rotina foi:

Tempo (em segundos) de execução de transferfullcircle de uma pilha de 1000 elementos, calculada 1000 vezes:
18.208990234998055
Tempo (em segundos) de execução de transferfullcircle_usandolista de uma pilha de 1000 elementos, calculada 1000 vezes:
7.325813493996975
Razão entre tempos:
0.40231849209939224