Operações de fila com duas pilhas
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
Transferir uma pilha para outra, item por item, inverte a ordem dos valores. Depois de transferir uma pilha de chegadas, qual valor fica no topo?
Use uma pilha para os valores que chegam e outra para atender os pops e peeks. A verdadeira questão é quando transferir da primeira para a segunda.
Transfira só quando a pilha de atendimento estiver vazia e, então, mova tudo de uma vez. Enquanto a pilha de atendimento tiver valores, o topo dela é sempre o valor mais antigo ainda na fila.
- Tempo-alvo
- O(m)
- Espaço-alvo
- O(m)
Restrições
- O(1) amortized time per operation
- stacks allow only push, pop and top
Solução
Os valores novos vão para uma pilha de entrada. Pops e peeks leem de uma pilha de saída, e só quando ela está vazia a pilha de entrada inteira é transferida para ela, o que inverte as chegadas e deixa o mais antigo no topo. Transferir para uma pilha de saída que ainda tem valores enterraria valores mais antigos sob os mais novos, então é a checagem de vazio que mantém a ordem certa. Cada valor é empilhado duas vezes e desempilhado no máximo duas vezes, então m operações custam O(m) no total, ou seja, O(1) amortizado por operação. O espaço é O(n) para os valores guardados.
def run_queue(ops):
inbox, outbox, out = [], [], []
for op in ops:
if op[0] == "push":
inbox.append(op[1])
continue
if not outbox:
while inbox: # reverse once: the oldest ends on top
outbox.append(inbox.pop())
if not outbox:
out.append(None) # the queue is empty
elif op[0] == "pop":
out.append(outbox.pop())
else:
out.append(outbox[-1])
return out
print(run_queue([["push", 1], ["push", 2], ["peek"], ["pop"], ["push", 3], ["pop"], ["pop"]])) # -> [1, 1, 2, 3]
print(run_queue([["push", 7], ["pop"], ["push", 8], ["push", 9], ["peek"]])) # -> [7, 8]
print(run_queue([["pop"], ["push", 4], ["peek"]])) # -> [None, 4]Travou na ideia, e não no código? Fila com duas pilhas explica isso.