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

Encontrando um elemento de uma pilha (usando uma fila)

+1 voto
29 visitas
perguntada Mai 24 em Ciência da Computação por Pablo Castro (66 pontos)  

Este é o exercício 6.27 do livro Data Structures and Algorithms in Python (Michael T. Goodrich, Roberto Tamassia e Michael H. Goldwasser):

Suponha que você tenha uma pilha \(S\) contendo \(n\) elementos e uma fila \(Q\) inicialmente vazia. Descreva como você pode usar \(Q\) para checar se \(S\) contém um certo elemento \(x\), com a restrição adicional que o seu algoritmo deve retornar os elementos de volta a \(S\) em suas posições originais. Você deve usar apenas \(S, Q\) e um número constante de outras variáveis.

Compartilhe

1 Resposta

+1 voto
respondida Mai 24 por Pablo Castro (66 pontos)  

Relembrando os conceitos, sabemos que uma pilha é uma coleção de objetos que são inseridos e removidos pelo principio LIFO (last in, first out). Enquanto filas seguem o principio FIFO (first in, first out).

Resumidamente, o algoritmo usado para resolver este problema é o seguinte:
1. Olhamos o primeiro elemento da pilha \(S\);
2. Se for \(x\), paramos, se não for, o jogamos na fila \(Q\) e checaremos o próximo;
3. Fazemos isso até que se encontre \(x\) ou \(S\) fique vazia;
4. Invertemos a posição dos elementos em \(Q\);
5. Retornamos os elementos de \(Q\) para \(S\).

Abaixo a implementação:
Primeiro, iremos definir as classes de pilhas e filas e seus atributos:

class Fila:
    def __init__(self):
        self.dados = []

    def insere(self, numero):
        return self.dados.append(numero)

    def retira(self):  # retorna o primeiro elemento da fila
        return self.dados.pop(0)

    def empty(self):
        if len(self.dados) == 0:
            return True
        else:
            return False

    def reversa(self):  # inverte os elementos da fila
        return self.dados.reverse()


class Pilha:
    def __init__(self):
        self.dados = []

    def insere(self, numero):
        return self.dados.append(numero)

    def retira(self):  # retorna o último elemento da pilha
        return self.dados.pop()

    def empty(self):
        if len(self.dados) == 0:
            return True
        else:
            return False

    def top(self):  # retorna o valor do topo da fila
        return self.dados[-1]

    def print(self):
        return print(self.dados)

Agora a implementação do algoritmo:

def contemx(myStack, myQueue, x):
# verificamos nos números enquanto S não estiver vazia
    while not myStack.empty():
        if myStack.top() == x:
            return "Sim"
        else:
            numero = myStack.retira()
            myQueue.insere(numero)
    return "Não"  # caso x não exista em S


def retornainicio(myStack, myQueue):  
# inverte Q e retorna os elementos para S
    myQueue.reversa()
    while not myQueue.empty():
        numero = myQueue.retira()
        myStack.insere(numero)
    return myStack.print()

Exemplo 1:

if __name__ == '__main__':   
    myStack = Pilha()
    myQueue = Fila()

    my_list = [1, 2, 5, 4]
    for i in my_list:
        myStack.insere(i)

    x = 5

    print(f'{x} está na pilha? ' + contemx(myStack, myQueue, x))
    retornainicio(myStack, myQueue)

Output:

5 está na pilha? Sim 
[1, 2, 5, 4]

Exemplo 2:

if __name__ == '__main__':   
    myStack = Pilha()
    myQueue = Fila()

    my_list = [1, 2, 5, 4]
    for i in my_list:
        myStack.insere(i)

    x = 9

    print(f'{x} está na pilha? ' + contemx(myStack, myQueue, x))
    retornainicio(myStack, myQueue)

Output:

9 está na pilha? Não 
[1, 2, 5, 4]
...