Pular para o conteudo principal
SeniorPath
Explorar conteudo
Menu / Fechar menu

24 de Março

Implementar fila usando pilhas

Como compor duas pilhas para simular fila e entender por que a transferencia sob demanda deixa o custo amortizado baixo.

Pilha Intermediario 15 min TypeScript

#interviews#stack#queue#design

Implemente uma fila usando apenas pilhas.

A estrutura precisa suportar:

  • push(x)
  • pop()
  • peek()
  • empty()

Na versão original, isso costuma vir como uma classe. Aqui no SeniorPath, use:

  • operations: lista de operações
  • values: valor associado a cada operação, ou null

E retorne um array com as respostas. Operações sem retorno devem devolver null.

Exemplo:

Input:
  operations = ["MyQueue","push","push","peek","pop","empty"]
  values     = [null,1,2,null,null,null]

Output:
  [null,null,null,1,1,false]

O que perceber antes de codar

  • Fila e FIFO. Stack e LIFO.
  • O problema e de composição de estruturas.
  • O ponto forte esta em evitar transferencia desnecessaria.

Erros comuns

  • mover todos os elementos de um lado para o outro em toda operação
  • esquecer que `peek` e `pop` devem ler da mesma extremidade lógica da fila

Passo 1 - Modelar primeiro o comportamento certo

Antes de pensar nas pilhas, vale fixar o comportamento:

  • entra no fim
  • sai do começo

Isso e fila.

Passo 2 - Escrever uma versão inicial simples

A versão inicial mais direta e usar um array como fila:

  • push adiciona no fim
  • pop remove do começo
  • peek olha o começo

Funciona para modelar a semântica.

Mas não respeita a restrição do problema.

Passo 3 - Perguntar como duas pilhas podem simular FIFO

A ideia chave e separar:

  • o que acabou de entrar
  • o que esta pronto para sair

Se você despeja uma pilha inteira na outra, a ordem se inverte.

E e justamente essa inversao que transforma LIFO em FIFO.

Passo 4 - Fazer transferencia só quando precisa

Se você transferir sempre, funciona, mas gasta demais.

A versão forte faz assim:

  • incoming recebe os pushes
  • outgoing serve pops e peeks
  • só transfere de incoming para outgoing quando outgoing estiver vazio

O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.

Codigo inicial

export function runMyQueue(operations, values) {
  // operations example: ["MyQueue", "push", "peek"]
  // values example: [null, 1, null]
  // sua solução aqui
  return []
}
solution.ts
Travado? Dicas disponiveis.

Ainda não resolveu?

Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.

Abrir a solucao de referencia

Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.

Solução

Complexidade final

Tempo: O(1) amortizado

Espaço: O(n)

Solução 1 - Simular com um array-fila

Boa versão inicial para fixar a semântica correta.

export function runMyQueue(operations, values) {
  const queue = []
  const output = []

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "MyQueue") {
      output.push(null)
    } else if (operation === "push") {
      queue.push(value)
      output.push(null)
    } else if (operation === "pop") {
      output.push(queue.shift() ?? null)
    } else if (operation === "peek") {
      output.push(queue[0] ?? null)
    } else if (operation === "empty") {
      output.push(queue.length === 0)
    }
  }

  return output
}

Correta para comportamento, mas não para a restrição de usar pilhas.

Solução 2 - Duas pilhas com transferencia sob demanda e custo amortizado em O(1)

Agora a estrutura respeita o problema e evita trabalho repetido.

export function runMyQueue(operations, values) {
  const incoming = []
  const outgoing = []
  const output = []

  function rebalance() {
    if (outgoing.length === 0) {
      while (incoming.length > 0) {
        outgoing.push(incoming.pop())
      }
    }
  }

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "MyQueue") {
      output.push(null)
    } else if (operation === "push") {
      incoming.push(value)
      output.push(null)
    } else if (operation === "pop") {
      rebalance()
      output.push(outgoing.pop() ?? null)
    } else if (operation === "peek") {
      rebalance()
      output.push(outgoing[outgoing.length - 1] ?? null)
    } else if (operation === "empty") {
      output.push(incoming.length === 0 && outgoing.length === 0)
    }
  }

  return output
}

O ponto mais importante aqui não e a sintaxe. E entender por que a transferencia só precisa acontecer de vez em quando.

O que dizer na entrevista

Uma explicação curta e boa seria:

Eu separo elementos novos em uma pilha de entrada e elementos prontos para sair em uma pilha de saída. Quando preciso fazer pop ou peek e a de saída esta vazia, transfiro tudo da entrada para ela. Essa inversao preserva o comportamento FIFO e o custo fica O(1) amortizado.

Isso mostra que você:

  • entendeu a composição das duas estruturas
  • sabe justificar a transferencia sob demanda
  • consegue falar de custo amortizado de forma concreta

Quando esse padrão aparece de novo

Esse padrão reaparece quando você precisa:

  • compor estruturas simples para criar comportamento novo
  • usar transferencia sob demanda
  • discutir custo amortizado
  • separar fase de escrita da fase de leitura

O ponto não e decorar MyQueue.

O ponto e aprender a construir um comportamento maior a partir de pecas pequenas.
Proximo desafio Ladrão de casas Desafio anterior Pilha com mínimo

Desafios relacionados

Pilha com mínimo

Parênteses válidos

Maior substring sem caracteres repetidos

Artigos relacionados

Enquadrar o problema antes de codificar

Como Explicar sua Solução sem se Perder

Reconhecer padrões em problemas