Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como manipular elementos entre 3 pilhas mantendo a ordem da 1ª intacta e colocando elementos da 3ª na 2ª de acordo com uma ordem específica?

0 votos
49 visitas
perguntada Mai 24 em Ciência da Computação por Monica Guo (41 pontos)  
editado Mai 24 por Monica Guo

Essa é uma questão abordada pelo exercício C-6.23 do livro "Data Structures and Algorithms in Python – Michael T. Goodrich, Roberto Tamassia and Michael H. Goldwasser”. O enunciado do exercício é:

Suponha que você tem três pilhas não vazias \(R, S\) e \(T\). Descreva a sequência de operações que resulta em S armazenando todos os elementos que estavam originalmente em T abaixo de todos os elementos que estavam originalmente em S, mantendo os conjuntos desses elementos nas suas ordens originais. A configuração final de R deve ser a mesma que a sua configuração original. Por exemplo, se \(R = [1, 2, 3]\), \(S = [4, 5]\), e \(T = [6, 7, 8, 9]\), então a configuração final deve ter: \(R = [1, 2, 3]\) e \(S = [6, 7, 8, 9, 4, 5]\).

Compartilhe

2 Respostas

+1 voto
respondida Mai 24 por Monica Guo (41 pontos)  
editado Mai 24 por Monica Guo

Uma sequência que pode ser utilizada para resolver o problema seria:

  1. Tirar elemento por elemento da pilha \(S\) e colocar na pilha \(R\);
  2. Tirar elemento por elemento da pilha \(T\) e colocar na pilha \( R\);
  3. Tirar elemento por elemento da pilha \(R\) e colocar na pilha \(S\) e parar após a remoção de todos os elementos que estavam originalmente nas pilhas \(S\) e \(T\).

Isso funciona pois os elementos das pilhas são inseridos e removidos de acordo com o princípio Last In First Out. Ou seja, o elemento do topo da pilha é removido primeiro. Para isso, definimos dentro da classe Stack (classe que implementa uma pilha) os métodos push (insere um elemento na pilha) e pop (retira um elemento da pilha).

class Stack:

    def __init__(self):
        self.__stack = []

    def __len__(self):
        return len(self.__stack)

    def is_empty(self):
        return len(self.__stack) == 0

    def push(self,element):
        self.__stack.append(element)

    def pop(self):
        if(self.is_empty()):
            raise(Empty('Stack is empty')) 
        else:
            return self.__stack.pop()

    def print_stack(self):           #imprime os elementos da lista na tela
        print(self.__stack)

Após criar a classe, criamos os objetos da classe (pilhas \(R, S\) e \(T\)) e inserimos os elementos dados pelo exercício como exemplo.

if __name__ == '__main__':

    # Criando a primeira pilha 
    Stack_R = Stack()

    Stack_R.push(1)
    Stack_R.push(2)
    Stack_R.push(3)    

    # Criando a segunda pilha
    Stack_S = Stack()

    Stack_S.push(4)
    Stack_S.push(5)

    # Criando a terceira pilha
    Stack_T = Stack()

    Stack_T.push(6)
    Stack_T.push(7)
    Stack_T.push(8)
    Stack_T.push(9)

Agora que já definimos as pilhas, vamos implementar a solução proposta.

    # Calculando o número de elementos inicial da segunda pilha
    original_len_S = len(Stack_S)

    # Tirando todos os elementos da segunda pilha e colocando na primeira 
    for i in range(original_len_S):
        x = Stack_S.pop()
        Stack_R.push(x)


    # Calculando o número de elementos inicial da terceira pilha
    original_len_T = len(Stack_T)

    # Tirando todos os elementos da terceira pilha e colocando na primeira 
    for i in range(original_len_T):
        y = Stack_T.pop()
        Stack_R.push(y)


    # Tirando os elementos da primeira pilha e colocando na segunda com 
    # exceção dos elementos  originais da primeira pilha 
    for i in range(original_len_S + original_len_T):
        z = Stack_R.pop()
        Stack_S.push(z)

Por fim, para checarmos o resultado, chamamos o método print_stack() da classe Stack para mostrar os elementos contidos em cada pilha.

    # Checando os elementos de cada pilha 
    Stack_R.print_stack()
    Stack_S.print_stack()
    Stack_T.print_stack()

O resultado final é:

[1, 2, 3]
[6, 7, 8, 9, 4, 5]
[]
0 votos
respondida Jun 11 por Felipe Amaral (16 pontos)  

Muito boa a sua implementação para a questão, Mônica!

Acho que um ponto muito positivo para a sua resposta foi a criação de uma classe própria para trabalhar com as manipulações solicitadas. Muitas vezes aproveitamos um classe pronta, mas elas tem muito mais funcionalidades de que precisamos, o que pode reduzir o desempenho de nossa execução.

Fiz uma comparação de sua implementação utilizando a sua classe e uma classe de pilha já pronta do módulo queue do Python. Basicamente o que fiz foi replicar o seu código somente substituindo a sua classe pela classe do queue. Na simulação que fiz o tempo de execução de seu código foi de menos de 20% do código utilizando o módulo queue.

O código da simulação que realizei foi o seguinte:

#A-) Encapsulando o seu código em uma função
def stackfunction_original(Stack_S, Stack_T, Stack_R):
    # Calculando o número de elementos inicial da segunda pilha
    original_len_S = len(Stack_S)

        # Tirando todos os elementos da segunda pilha e colocando na primeira 
    for i in range(original_len_S):
            x = Stack_S.pop()
            Stack_R.push(x)


        # Calculando o número de elementos inicial da terceira pilha
    original_len_T = len(Stack_T)

        # Tirando todos os elementos da terceira pilha e colocando na primeira 
    for i in range(original_len_T):
            y = Stack_T.pop()
            Stack_R.push(y)
    # Tirando os elementos da primeira pilha e colocando na segunda com 
        # exceção dos elementos  originais da primeira pilha 
    for i in range(original_len_S + original_len_T):
            z = Stack_R.pop()
            Stack_S.push(z)
    return Stack_S, Stack_T,Stack_R

#B-) Testando a função stackfunction_original
    # Criando a primeira pilha 
Stack_R = Stack()

Stack_R.push(1)
Stack_R.push(2)
Stack_R.push(3)    

    # Criando a segunda pilha
Stack_S = Stack()

Stack_S.push(4)
Stack_S.push(5)

    # Criando a terceira pilha
Stack_T = Stack()

Stack_T.push(6)
Stack_T.push(7)
Stack_T.push(8)
Stack_T.push(9)

Stack_S, Stack_T, Stack_R=stackfunction_original(Stack_S, Stack_T, Stack_R)
# Checando os elementos de cada pilha 
Stack_R.print_stack()
Stack_S.print_stack()
Stack_T.print_stack()

#C-) Criando uma função semelhante, porém utilizando uma classe de pilha já pronta do módulo queue
import queue as q
def stackfunction_usandomoduloqueue(Stack_S, Stack_T, Stack_R):
    # Calculando o número de elementos inicial da segunda pilha
    original_len_S = Stack_S.qsize()

        # Tirando todos os elementos da segunda pilha e colocando na primeira 
    for i in range(original_len_S):
            x = Stack_S.get()
            Stack_R.put(x)


        # Calculando o número de elementos inicial da terceira pilha
    original_len_T = Stack_T.qsize()

        # Tirando todos os elementos da terceira pilha e colocando na primeira 
    for i in range(original_len_T):
            y = Stack_T.get()
            Stack_R.put(y)
    # Tirando os elementos da primeira pilha e colocando na segunda com 
        # exceção dos elementos  originais da primeira pilha 
    for i in range(original_len_S + original_len_T):
            z = Stack_R.get()
            Stack_S.put(z)
    return Stack_S, Stack_T,Stack_R

#D-) Testando a função stackfunction_usandomoduloqueue
    # Criando a primeira pilha 
Stack_R = q.LifoQueue(maxsize=0)

Stack_R.put(1)
Stack_R.put(2)
Stack_R.put(3)    

    # Criando a segunda pilha
Stack_S = q.LifoQueue(maxsize=0)

Stack_S.put(4)
Stack_S.put(5)

    # Criando a terceira pilha
Stack_T = q.LifoQueue(maxsize=0)

Stack_T.put(6)
Stack_T.put(7)
Stack_T.put(8)
Stack_T.put(9)

Stack_S, Stack_T, Stack_R=stackfunction_usandomoduloqueue(Stack_S, Stack_T, Stack_R)
# Checando os elementos de cada pilha 
print(list(Stack_R.queue))
print(list(Stack_S.queue))
print(list(Stack_T.queue))

#E-) Criando execuções para comparação

def stackfunction_original_testedevelocidade():
   #Cria três pilhas com mil elementos distribuidos
   Stack_R = Stack()
   Stack_S = Stack()
   Stack_T = Stack()

   for i in range(1000):
       if i<300:
         Stack_R.push(i)
       if (i>=300 and i<500):
         Stack_S.push(i)
       if i>=500:
         Stack_T.push(i)
   #Executa a função stackfunction_original
   Stack_S, Stack_T, Stack_R=stackfunction_original(Stack_S, Stack_T, Stack_R)
   return 0

def stackfunction_usandomoduloqueue_testedevelocidade():
   #Cria três pilhas com mil elementos distribuidos
   Stack_R = q.LifoQueue(maxsize=0)
   Stack_S = q.LifoQueue(maxsize=0)
   Stack_T = q.LifoQueue(maxsize=0)
   for i in range(1000):
       if i<300:
         Stack_R.put(i)
       if (i>=300 and i<500):
         Stack_S.put(i)
       if i>=500:
         Stack_T.put(i)
   #Executa a função stackfunction_usandomoduloqueue
   Stack_S, Stack_T, Stack_R=stackfunction_usandomoduloqueue(Stack_S, Stack_T, Stack_R)
   return 0 

#F-) Testando o tempo de execução de cada rotina
import timeit
tempo1=timeit.timeit('stackfunction_original_testedevelocidade()', number=1000, setup="from __main__ import stackfunction_original_testedevelocidade")
tempo2=timeit.timeit('stackfunction_usandomoduloqueue_testedevelocidade()', number=1000, setup="from __main__ import stackfunction_usandomoduloqueue_testedevelocidade")
print("Tempo (em segundos) de execução de stackfunction_original para três pilhas com total de 1000 elementos, calculada 1000 vezes:")
print(tempo1)
print("Tempo (em segundos) de execução de stackfunction_usandomoduloqueue para três pilhas com total de 1000 elementos, calculada 1000 vezes:")
print(tempo2)
print("Razão entre tempos:")
print(tempo1/tempo2)

E o resultado da execução do código foi:

Tempo (em segundos) de execução de stackfunctionoriginal para três pilhas com total de 1000 elementos, calculada 1000 vezes:
1.7810534890013514
Tempo (em segundos) de execução de stackfunction
usandomoduloqueue para três pilhas com total de 1000 elementos, calculada 1000 vezes:
9.706052907000412
Razão entre tempos:
0.18349925619267757

...