Uma fila com duas pilhas

Há alguns anos, na entrevista de emprego do Google, um amigo recebeu o seguinte desafio: “implemente uma fila com duas pilhas”. Achei o desafio interessante, então decidi pensar sobre esse problema (para o problema inverso veja o próximo post). Antes de continuar lendo, pense como você resolveria esse desafio.

...

Pronto?

Vamos começar com uma breve revisão de pilhas e filas.

Pilhas e filas

Uma pilha é uma coleção de elementos baseada no conceito de Last In First Out (LIFO), ou seja, o último elemento a ser adicionado é o primeiro a sair. Ela possui duas operações básicas: empilhar (push - adiciona um elemento no final da pilha) e desempilhar (pop - remove e devolve o último elemento da pilha).

Analogamente, uma fila é uma estrutura de dados baseada em First In First Out (FIFO), ou seja, o primeiro elemento a ser adicionado é o primeiro a sair (pense em uma fila de banco, por exemplo). Ela também possui duas operações básicas: insere (adiciona um elemento no final da fila) e remove (remove o primeiro elemento da fila).

Implementação

Vamos usar a seguinte implementação de uma pilha em Python (não se preocupe se você não souber Python - o resto do código não depende de nenhuma funcionalidade específica):

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

    def empilha(self, elemento):
        self.elementos.append(elemento)

    def desempilha(self):
        return self.elementos.pop()

    def vazio(self):
        return len(self.elementos) == 0

Adicionei uma função extra vazio para dizer se a pilha está vazia ou não. Agora, vamos à implementação da fila com duas pilhas:

class Fila(object):
    def __init__(self):
        self.normal = Pilha()
        self.invertida = Pilha()

    def insere(self, elemento):
        transfere(self.invertida, self.normal)
        self.normal.empilha(elemento)

    def remove(self):
        transfere(self.normal, self.invertida)
        return self.invertida.desempilha()

    def vazio(self):
        return self.normal.vazio() and self.invertida.vazio()

def transfere(origem, destino):
    while (not origem.vazio()):
        destino.empilha(origem.desempilha())

Explicação

O “truque” é usar uma pilha como a fila normal e outra como a fila invertida. Após qualquer operação todos os elementos estão ou na fila normal ou na fila invertida, ou seja, sempre ao menos uma das duas pilhas está vazia. Esse invariante é essencial para o funcionamento da nossa implementação. Vamos então entender cada função.

A função auxiliar transfere desempilha todos os elementos da origem e os empilha, em ordem, no destino. Assumindo que uma das pilhas está vazia temos dois casos:

1. A pilha origem está vazia: nada acontece.
2. A pilha destino está vazia: os elementos da origem são removidos de trás para a frente e adicionados nessa ordem na pilha destino. Em outras palavras, a pilha origem é invertida na pilha destino.

Assim, podemos entender que a função transfere sempre inverte o conteúdo da origem e adiciona no destino. Note que ao final dessa operação a pilha origem sempre está vazia, assim o invariante de que uma das pilhas está vazia continua válido.

A função insere deve adicionar um elemento no final da fila. A função empilha insere um elemento no final de uma pilha. Assim, basta empilhar o novo elemento na pilha normal. Novamente, considerando nosso invariante, temos dois casos:

1. A pilha invertida está vazia: a função transfere não faz nada e todos os elementos já estão em ordem na pilha normal.
2. A pilha normal está vazia: a função transfere inverte a pilha invertida (ou seja, coloca na ordem correta) e adiciona na pilha normal.

Em ambos os casos, após a chamada de transfere a pilha invertida está vazia e a pilha normal contém todos os elementos. O novo elemento é adicionado ao final da pilha normal e o invariante ainda é válido.

Finalmente a função remove deve remover o primeiro elemento da fila. Esse é o motivo de termos uma pilha que guarda a fila invertida, pois remover o último elemento da fila invertida (desempilhar) é o mesmo que remover o primeiro elemento da fila não invertida. Agora queremos garantir que os elementos estejam na pilha invertida, ou seja, invertemos e transferimos os elementos da pilha normal para a pilha invertida. De acordo com o nosso invariante temos, mais uma vez:

1. A pilha invertida está vazia: a função transfere inverte a pilha normal e transfere os elementos para a pilha invertida.
2. A pilha normal está vazia: a função transfere não faz nada.

O último elemento da pilha invertida (primeiro elemento da fila) é então removido e assim o invariante continua verdadeiro. Como a função vazio não altera nenhuma das pilhas e na condição inicial ambas as pilhas estão vazias, o invariante é sempre verdadeiro.

Simulação

Para facilitar o entendimento vamos mostrar uma simulação. Vamos inserir os números de 0 a 4 na fila. A partir do terceiro elemento, ao adicionar um elemento vamos imediatamente remover um elemento da fila.

Inicialmente inserimos os números 0, 1 e 2 na fila. Como a pilha invertida (I) está vazia, eles simplesmente serão empilhados na pilha normal (N):

Ao remover um elemento todos os elementos da pilha normal são transferidos para a invertida

e então o último elemento é removido (desempilhado).

Note que na remoção o número 0, ou seja o primeiro elemento adicionado, foi removido. Adicionamos então os números 3 e 4. Para isso os elementos da pilha invertida são transferidos para a pilha normal

e os novos elementos são adicionado (empilhado) no final da pilha normal (tecnicamente seria necessário transferir os elementos da pilha invertida para a normal, mas a pilha invertida já está vazia então vamos ignorar esse passo)

Vamos agora remover todos os elementos até que a fila esteja vazia. Para isso devemos novamente transferir os elementos da pilha normal para a invertida

e então desempilhar os elementos do último para o primeiro

Se voltarmos à simulação veremos que os elementos foram removidos da fila na mesma ordem em que foram inseridos, ou seja, temos uma FIFO (o primeiro a entrar é o primeiro a sair).

Essa foi a nossa implementação de uma fila com duas pilhas. E aí, você saberia implementar uma pilha com duas filas?