Simulação Mútua de Pilha e Fila

Implementar uma fila usando duas pilhas e uma pilha usando duas filas são perguntas clássicas de entrevistas sobre projeto. Elas avaliam sua compreensão das invariantes de ambas as estruturas de dados e sua capacidade de manter a garantia de uma estrutura usando as operações básicas de outra. Os entrevistadores também usam essas perguntas como ponto de partida para discutir a complexidade amortizada.

A ideia principal é: pilhas são LIFO e filas são FIFO. Para converter uma na outra, é necessário inverter a ordem — e inverter uma pilha em outra pilha produz a ordem original de inserção, que é FIFO.

A abordagem preguiçosa usa uma pilha inbox para as inserções e uma pilha outbox para as remoções. Quando a remoção da fila é chamada, se outbox estiver vazia, transfira todos os elementos de inbox para outbox — essa inversão restaura a ordem FIFO. Se outbox não estiver vazia, remova o elemento diretamente dela. As transferências ocorrem sob demanda, amortizando o custo de transferência O(n) ao longo de muitas operações.

Cada elemento é transferido de inbox para outbox no máximo uma vez. Como remover elementos de outbox custa O(1) e as transferências ocorrem apenas quando outbox está vazia, o trabalho total para n operações de push e n operações de pop é de no máximo 2n operações de pilha — O(n) no total e O(1) amortizado por operação. Isso significa que operações individuais podem custar O(n) no pior caso, mas a média é O(1).

Implementar uma pilha com duas filas é menos natural, pois filas são FIFO. A abordagem de remoção preguiçosa mantém uma fila principal e uma fila temporária. Em push, insira o elemento na fila principal (O(1)). Em pop ou peek, remova todos os elementos, exceto o último, para a fila temporária, salve o último elemento e, em seguida, troque as filas. Isso custa O(n) por remoção, mas O(1) por inserção.

Uma implementação elegante com uma fila: em push, insira o novo elemento e, em seguida, rotacione a fila para que o novo elemento fique na frente. Rotacionar significa remover e inserir novamente todos os elementos que já estavam na fila antes da inserção. Assim, pop e peek custam O(1) (basta remover ou consultar o primeiro elemento). Push custa O(n) — a compensação oposta à da versão com duas filas.

Para uma fila criada com duas pilhas: push O(1), pop/peek O(1) amortizado — prefira-a quando as operações de pop forem frequentes. Para uma pilha criada com duas filas: push O(1), pop O(n) — prefira-a quando houver muito mais operações de push do que de pop. Para uma pilha criada com uma fila: push O(n), pop O(1) — prefira-a quando as operações de pop predominarem. Expresse essas compensações claramente em uma entrevista para demonstrar que você pensa além de simplesmente dizer «funciona».

Quando os elementos 1, 2 e 3 são inseridos em uma pilha (caixa de entrada), eles ficam organizados da base ao topo como 1, 2 e 3. Remover todos eles para uma segunda pilha (caixa de saída) inverte a ordem: a caixa de saída fica com 3 na base e 1 no topo. Remover elementos da caixa de saída produz 1, depois 2 e depois 3 — exatamente a ordem de inserção FIFO. É por isso que exatamente duas inversões (duas pilhas) restauram FIFO, enquanto uma única pilha produziria LIFO.

LeetCode 232 é o problema direto de «fila criada com duas pilhas». A solução esperada é a transferência preguiçosa para a caixa de saída. Em uma entrevista, explique que cada elemento passa da caixa de entrada para a caixa de saída no máximo uma vez, tornando todas as operações O(1) amortizadas. Mencione que chamadas individuais de pop podem custar O(n) no pior caso, quando a caixa de saída está vazia, mas a média ao longo de n operações é O(1).

LeetCode 225 é o problema de «pilha criada com filas». A solução de uma fila com rotação ao usar push é a mais simples. Depois de inserir o elemento x, rotacione a fila, movendo para trás de x todos os elementos que já estavam nela. Isso custa O(n) por push, mas faz com que top e pop custem O(1). Explique a compensação e confirme que ela corresponde às restrições, por exemplo, uma carga de trabalho com poucas operações de push ou muitas operações de pop.

Um desafio de projeto relacionado: implemente três pilhas usando um único vetor. Uma abordagem divide o vetor em três seções fixas de mesmo tamanho. Uma abordagem mais flexível usa armazenamento intercalado com ponteiros, fazendo cada pilha crescer a partir de sua região e copiando os dados quando os limites colidem. Isso testa o gerenciamento de vetores dinâmicos e é uma questão comum em entrevistas de nível sênior. A abordagem das seções fixas é mais simples, mas desperdiça espaço se as pilhas crescerem de forma desigual.

Os problemas de simulação mútua ensinam um princípio mais amplo: qualquer estrutura de dados pode ser construída a partir de outra, desde que haja armazenamento intermediário e operações de reversão suficientes. O custo da simulação depende de quais operações você otimiza — sempre é possível tornar push O(1) ou pop O(1), mas tornar ambos O(1) exige amortização ou várias estruturas auxiliares.

Em uma entrevista, pergunte sempre: "Quais operações são mais frequentes?" Isso orienta a escolha da variante de implementação e demonstra uma visão de nível sênior sobre os requisitos operacionais.

Nesta lição, você aprendeu: uma fila criada a partir de duas pilhas consegue fazer pop amortizado em O(1) ao transferir elementos da entrada para a saída sob demanda, uma pilha criada a partir de uma fila consegue fazer pop em O(1) ao girar a fila a cada push (push O(n)) e a escolha da operação que deve ser O(1) depende do padrão de uso. Em seguida, exploraremos os componentes internos dos mapas hash e o tratamento de colisões.