Algoritmos e Estruturas de Dados

Fila (Queue)

A fila é uma das estruturas de dados mais importantes em muitos algoritmos. É muito parecida com uma fila do dia a dia. O primeiro elemento adicionado à fila será o primeiro a ser “servido” e removido.
Imagine uma fila de formigas esperando um café. A primeira formiga na fila receberá o café e sairá dela, em seguida a próxima formiga receberá o café e também sairá, e assim por diante, até que não haja formigas esperando.
notion image
Declarar e utilizar uma fila na maioria das linguagens de programação costuma ser simples, pois muitas (como Python, C++, Java, etc.) já fornecem uma implementação pronta para esse tipo de estrutura. Ainda assim, podemos implementar nossa própria fila usando uma lista ligada. Consegue pensar em como fazer isso?
from queue import Queue

q = Queue()    # Cria uma nova fila
q.put(1)       # Adiciona 1 à frente da fila
q.put(2)       # Adiciona 2 em seguida
q.put(3)       # Adiciona 3 após 2

# Remove elementos da fila usando get()
print(q.get()) # imprime 1
print(q.get()) # imprime 2
print(q.get()) # imprime 3

Desafio: Simulação de Fila

Você está implementando um sistema que deve acompanhar os clientes na loja. Esse sistema precisa fazer duas coisas: adicionar um cliente à fila de espera e remover o primeiro cliente da fila quando ele for atendido. Cada vez que você remover alguém da fila, deve imprimir o nome dessa pessoa.

Entrada

A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 100 000).
As próximas n linhas contêm operações — ou add ou pop:
  • A operação add é seguida por um nome, e você deve adicionar esse cliente à fila de espera.
  • A operação pop apenas contém o nome da operação, sem nada mais.
É garantido que sempre haverá alguém na fila antes de uma operação pop, então as operações são válidas.
Os nomes não excedem 20 símbolos.

Saída

Para cada operação pop, o programa deve imprimir o nome do cliente que estiver na frente da fila.

Exemplos

Entrada
Saída
9 add Steven add Sam pop add Sergio add Don pop add John pop pop
Steven Sam Sergio Don
4 add John Ford add Tom Ford pop pop
John Ford Tom Ford
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue