Algoritmi e Strutture Dati

Coda (Queue)

Una coda è una delle strutture dati fondamentali in molti algoritmi. È molto simile a una fila nella vita reale. Il primo elemento aggiunto a una coda sarà il primo a essere “servito” e rimosso.
Immagina una fila di formiche in coda per prendere un caffè. La prima formica in fila otterrà il caffè e uscirà dalla coda, poi la successiva otterrà il caffè e uscirà, e così via fino a quando la coda sarà vuota e non ci saranno più formiche in attesa di un caffè.
notion image
Dichiarare e usare una coda è piuttosto semplice nella maggior parte dei linguaggi, poiché molti linguaggi di uso generale (come Python, C++, Java, ecc.) hanno già implementato la struttura dati della coda per facilitarne l’utilizzo. È comunque possibile implementare la coda autonomamente utilizzando una linked list. Sai immaginare come farlo 🤔?
from queue import Queue

q = Queue()    # Create a new queue
q.put(1)       # Add 1 to the front of the queue
q.put(2)       # Add 2 next
q.put(3)       # Add 3 after 2

# Remove elements from the queue using get()
print(q.get()) # prints 1
print(q.get()) # prints 2
print(q.get()) # prints 3

Sfida: Simulazione di una coda

Stai realizzando un sistema che deve tenere traccia dei clienti all’interno del negozio. Questo sistema deve fare due cose: aggiungere un cliente in attesa e rimuovere il primo cliente in coda quando è stato servito. Ogni volta che rimuovi un cliente, devi stamparne il nome.

Input

La prima riga dell’input contiene un singolo intero n (1 ≤ n ≤ 100 000).
Le successive n righe contengono le operazioni - o add o pop:
  • L’operazione add è seguita da un nome, e devi aggiungere il cliente alla coda.
  • L’operazione pop contiene solo la parola pop e nulla più.
Si garantisce che ci sia sempre almeno un cliente in coda prima di ogni operazione pop, quindi le operazioni sono sempre valide.
I nomi non superano i 20 simboli.

Output

Per ogni operazione pop, il programma deve stampare il nome del cliente che si trova in testa alla coda.

Esempi

Input
Output
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