Stack e code

Panoramica

Pila e code sono strutture di dati comuni in informatica che specificano l'ordine in cui è possibile aggiungere e rimuovere elementi. Puoi utilizzarle per controllare l'ordine di interazione con i dati:

• Pila: contenitore dove gli elementi vengono inseriti e rimossi seguendo la logica first-in, last-out (FILO), simile a prendere un libro dalla cima di una pila di volumi da leggere.

• Coda: contenitore in cui si inseriscono e si rimuovono elementi in ordine FIFO (first-in, first-out), ad esempio l'elaborazione di una fila di clienti in attesa di un pasto.

Sebbene i codici previsti per stack e code siano apparentemente simili, presentano in realtà alcune differenze e punti forti chiave che puoi sfruttare per rendere le tue esperienze di gioco più performanti e intuitive.

Pile

Puoi immaginare uno stack come una pila di pancake. Supponiamo che tu sia in un bar e che il cameriere ti offra una pila infinita di pancake. Per educazione, prenderesti un pancake alla volta, sempre dalla cima della pila. Puoi chiedere al cameriere di aggiungere un nuovo pancake in cima alla pila e, quando hai fame, puoi prendere un pancake dalla cima nel piatto per mangiarlo. Se desideri un pancake specifico che si trova al centro della pila, dovrai mangiare prima quelli che si trovano sopra fino a raggiungere quello che vuoi. Il primo pancake aggiunto sarà anche l'ultimo che prenderai dalla pila. Come illustrato in questo esempio, ogni pila segue una logica di struttura dati first-in, last-out (FILO).

Quando utilizzare

Gli stack sono utili quando è necessario ripercorrere i propri passi o tenere traccia dell'ordine in cui si sono verificati gli eventi. Si tratta di casi come funzioni di annullamento, in catene di eventi o in sequenze di scelte. Ad esempio, immagina un robot che debba navigare un labirinto con diversi percorsi che si diramano. Ogni volta che il robot arriva a un bivio, sceglie una direzione e registra questa scelta nello stack. Se si imbatte in un vicolo cieco, il robot può tornare indietro seguendo lo stack, rimuovendo le scelte precedenti fino a quando non trova un percorso alternativo da esplorare.

Implementazione di Verse

Sebbene l'API Verse non fornisca un'implementazione predefinita degli stack, hai la possibilità di crearne una autonomamente.

Puoi rappresentare gli elementi in una pila utilizzando qualsiasi struttura di dati ordinati, come un array o un elenco collegato. In questo esempio, utilizzerai un array che rappresenta una soluzione ottimale per accedere alla cima dello stack.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

L'array Elements memorizza gli oggetti nella pila che sono di tipo t. Ciò significa che puoi inizializzare una pila con qualsiasi tipo di elemento, come int, float, stack ecc. L'uso di type come argomento per la classe stack è un esempio di tipo parametrico](parametric-types-in-verse).

Innanzitutto definiamo alcune funzioni di aiuto. Devi conoscere dove si trova la parte iniziale della pila per applicare funzioni di Push() e Pop() agli elementi a partire da quel punto. A tale scopo, avrai bisogno delle tre funzioni seguenti: Size(), IsEmpty() e Peek().

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

La funzione Size() restituisce semplicemente il valore Length dell'array Elements. La funzione IsEmpty() chiama la funzione Size() e presenta lo specificatore <transacts>, quindi avrà un esito negativo se Size() non equivale a 0.

La funzione Peek() restituisce l'elemento in cima all'indice (Length - 1) dell'array di elementi. Questa funzione presenta gli specificatori <decides><transacts> dal momento che l'accesso all'array può non riuscire se quest'ultimo è vuoto.

Per istanziare una pila puoi utilizzare una funzione costruttore. Un costruttore è una funzione speciale che crea un'istanza della classe a cui è associato. Il costruttore definisce i valori iniziali di un oggetto e ti permette di accedere al valore di Elements e di assegnarlo a un array iniziale di elementi.

# Creates and returns a stack from an initial array of elements InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

Push e Pop

Per aggiungere e rimuovere elementi dalla pila, devi inserire il nuovo elemento nella parte superiore della pila oppure rimuoverlo dalla parte superiore.

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

La funzione Push() prende l'elemento che vuoi mettere in cima alla pila e restituisce una nuova pila con l'elemento in cima. La restituzione di una nuova pila in alternativa alla modifica della pila attuale rappresenta un esempio di programmazione funzionale e riduce il rischio di effetti collaterali.

Per implementare la funzione Pop(), devi innanzitutto trovare il primo elemento della pila utilizzando la funzione Peek(). Devi quindi rimuovere l'elemento in cima (utilizzando la funzione RemoveElement[]) e restituire anche una nuova pila senza l'elemento. Puoi utilizzare una tupla per restituire contemporaneamente sia il nuovo stack sia l'elemento rimosso. A causa delle espressioni fallibili per l'accesso all'array e la chiamata a Peek(), Pop() deve presentare gli specificatori <decides><transacts>.

Codice completo

Di seguito viene fornito il codice completo della classe Stack.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

Code

Puoi immaginare una coda come un nastro trasportatore di sushi. Supponiamo che tu sia in un ristorante di sushi, dove i piatti di sushi vengono inviati uno alla volta sul nastro trasportatore, arrivando nell'ordine in cui sono stati preparati. Puoi rimuovere il piatto che si trova all'inizio della fila per mangiarlo, ma solo uno alla volta. Quando vuoi ordinare un nuovo piatto, chiedi allo chef di aggiungerlo alla fine della fila. Se ci sono già altri piatti di sushi in attesa, dovrai mangiare quelli in testa alla fila prima di arrivare al piatto che hai appena ordinato e che si trova alla fine. Il primo piatto di sushi aggiunto sarà anche il primo che prenderai. Come illustrato in questo esempio, ogni coda segue una logica di struttura dati first-in, first-out (FIFO).

Quando utilizzare

Le code rappresentano la soluzione ideale quando è necessario elaborare i dati in base all'ordine di arrivo. Può trattarsi di situazioni come servire i clienti in un drive-thru, gestire le chiamate in arrivo in un call center o porre una serie di domande in un'intervista. Ad esempio, se devi organizzare una sala d'attesa virtuale per i giocatori che devono completare un'attività o vivere un'esperienza di gioco uno alla volta, puoi utilizzare una coda per organizzarli seguendo la logica first-come, first-served basandoti sul momento del loro arrivo.

Implementazione di Verse

Sebbene l'API Verse non fornisca un'implementazione predefinita delle code, hai la possibilità di crearne una autonomamente.

Come per gli stack, puoi rappresentare gli elementi in una coda utilizzando qualsiasi struttura di dati ordinati, come un array o un elenco collegato. In questo esempio, utilizzerai un array che rappresenta una soluzione ottimale per accedere all'inizio e alla fine della coda. Per l'implementazione di una coda che utilizza un elenco collegato, dai un'occhiata a questo snippet di codice.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

L'array Elements memorizza gli oggetti nella coda di tipo t. Ciò significa che puoi inizializzare una coda con qualsiasi tipo di elemento, come int, float, queue ecc. L'uso di type come argomento per la classe stack è un esempio di tipo parametrico](parametric-types-in-verse).

Come nel caso degli stack, anche per le code è necessario specificare alcune funzioni di aiuto. Devi sapere dove si trovano l'inizio e la fine della coda per eseguire le funzioni Enqueue() e Dequeue(). Inoltre, ti sarà utile conoscere la dimensione della coda e se è vuota. Definirai queste quattro condizioni con le funzioni seguenti: Size(), IsEmpty(), Front() e Back().

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

La funzione Size() restituisce il valore Length dell'array Elements. La funzione IsEmpty() chiama la funzione Size() e presenta lo specificatore <transacts>, quindi avrà un esito negativo se Size() non equivale a 0.

Le funzioni Front() e Rear() restituiscono l'elemento all'indice anteriore (indice 0) e posteriore (Length - 1) dell'array di elementi. Entrambe le funzioni presentano gli specificatori <decides><transacts> dal momento che l'accesso all'array può non riuscire se quest'ultimo è vuoto.

Come stack, anche la classe queue deve utilizzare una funzione costruttore per assegnare l'array Elements. La funzione costruttore ti permette di accedere al valore di Elements e di assegnarlo a un array iniziale di elementi.

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Enqueue e Dequeue

Per aggiungere e rimuovere elementi dalla coda, devi inoltrare il nuovo elemento in fondo alla coda, oppure rimuovere un elemento dalla parte anteriore.

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

La funzione Enqueue() prende l'elemento che vuoi inserire nella coda e restituisce una nuova coda con il nuovo elemento in fondo. La restituzione di una nuova coda in alternativa alla modifica della coda attuale rappresenta un esempio di programmazione funzionale e riduce il rischio di effetti collaterali.

Per la funzione Dequeue(), devi rimuovere e restituire l'elemento in testa alla coda e restituire anche una nuova coda con il primo elemento rimosso (utilizzando la funzione RemoveElement[]). A causa delle espressioni fallibili per l'accesso all'array e la chiamata a Front(), Dequeue() deve presentare gli specificatori <decides><transacts>.

Codice completo

Di seguito viene fornito il codice completo della classe Coda.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

In autonomia

Esistono numerosi approcci per sviluppare e perfezionare gli stack e le code e devi esplorare varie strategie per arricchirli con nuove funzionalità. Ecco alcune idee per iniziare:

• Puoi trasformare una coda in una coda circolare, dove l'ultimo elemento si collega al primo, creando un ciclo continuo?

• Che ne dici di una coda di priorità, dove gli oggetti vengono ordinati non solo in base al loro ordine di arrivo, ma anche in base a un altro criterio?

• Puoi creare giochi che utilizzano una pila, come ad esempio la Torre di Hanoi? Che te ne pare di un gioco di gestione di un ristorante dove i clienti attendono in coda?