Pular para o conteúdo

Operações de fila com duas pilhas

Fácil#two-stacks#amortized~15 min

A missão

Problema

Monte uma fila em que o primeiro a entrar é o primeiro a sair usando duas pilhas e só três operações delas: empilhar (push) no topo, desempilhar (pop) do topo e ler o topo. Processe uma lista de operações: ["push", x] adiciona x, ["pop"] remove e informa o valor mais antigo, e ["peek"] informa esse valor sem removê-lo. Retorne os valores informados em ordem, informando None quando pop ou peek encontram a fila vazia. Cada operação deve custar O(1) amortizado.

Exemplos

Input:  ops = [["push", 1], ["push", 2], ["peek"], ["pop"],
               ["push", 3], ["pop"], ["pop"]]
Output: [1, 1, 2, 3]
Por quê: os valores saem na ordem em que chegaram
Input:  ops = [["push", 7], ["pop"], ["push", 8], ["push", 9], ["peek"]]
Output: [7, 8]
Por quê: depois que o 7 sai, o 8 é o valor mais antigo que resta
Input:  ops = [["pop"], ["push", 4], ["peek"]]
Output: [None, 4]
Por quê: edge case: remover de uma fila vazia informa None

Dicas

0 / 3

Tempo-alvo
O(m)
Espaço-alvo
O(m)

Restrições

  • O(1) amortized time per operation
  • stacks allow only push, pop and top

Travou na ideia, e não no código? Fila com duas pilhas explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado