08: Pile e Code

False (B)

Genera un errore di underflow

<p>O(1)</p> Signup and view all the answers

<p>E MPTY(S) = Controlla se la lista è vuota TOP(S) = Restituisce l'elemento in cima alla lista POP(S) = Rimuove e restituisce l'elemento in cima alla lista</p> Signup and view all the answers

<p>POP(S) (A)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Una lista</p> Signup and view all the answers

<p>Una struttura dati e una collezione di procedure designate per operare su di essa. (D)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>push</p> Signup and view all the answers

<p>pop</p> Signup and view all the answers

<p>push = Inserire un elemento nella pila pop = Estrarre un elemento dalla pila pila = Struttura dati LIFO ADT = Tipo di dato astratto</p> Signup and view all the answers

<p>Pila (A)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>Analoga a quella fra problema algoritmico e algoritmo</p> Signup and view all the answers

<p>dequeue() (prima volta) (B)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>9, 5, 3</p> Signup and view all the answers

<p>enqueue</p> Signup and view all the answers

<p>1 (B)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>2</p> Signup and view all the answers

<p>enqueue() = Inserisce un elemento nella coda dequeue() = Estrae un elemento dalla coda front() = Restituisce il primo elemento della coda queue() = Aggiunge un elemento alla coda</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>¬ (negazione)</p> Signup and view all the answers

<p>unsigned int</p> Signup and view all the answers

<p>unsigned int = Valori 0, 1, 2, ... boolean = Valori T, F float = Numeri con parte decimale char = Un singolo carattere</p> Signup and view all the answers

<p>Negazione (A)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Tipo di dato astratto</p> Signup and view all the answers

<p>Dequeue() nell'ultima posizione (D)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Indica l'inizio della coda.</p> Signup and view all the answers

<p>circolare</p> Signup and view all the answers

<p>Queue(3) = Aggiungi 3 alla coda Dequeue() = Rimuovi elemento dalla coda Queue(5) = Aggiungi 5 alla coda Queue(9) = Aggiungi 9 alla coda</p> Signup and view all the answers

<p>Dequeue() rimuove il primo elemento presente (C)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>5</p> Signup and view all the answers

<p>Se S IZE(Q) è uguale a Q.M - 1 (C)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Q.tail - Q.head</p> Signup and view all the answers

<p>un elemento</p> Signup and view all the answers

<p>E NQUEUE = Aggiungere un elemento alla coda D EQUEUE = Rimuovere un elemento dalla coda F RONT = Restituisce l'elemento in testa alla coda S IZE = Restituisce il numero di elementi nella coda</p> Signup and view all the answers

<p>Genera un errore di underflow (A)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>erroroverflow</p> Signup and view all the answers

Verifica se una pila è vuota.

Restituisce l'elemento in cima alla pila senza rimuoverlo.

Se la pila è vuota, restituisce un errore. Altrimenti, restituisce l'elemento in cima alla pila e lo rimuove.

La complessità temporale delle operazioni su una pila implementata con una lista è O(1).

La complessità spaziale di una pila implementata con una lista è O(n), dove n è il numero di elementi nella pila.

Un tipo di dato che definisce un insieme di valori e un insieme di operazioni che possono essere eseguite su quei valori.

Una struttura dati specifica che implementa un ADT.

Un ADT definisce un insieme di valori e operazioni possibili su quei valori. Un'implementazione concreta di un ADT è una specifica struttura dati che memorizza i dati e un insieme di procedure che implementano le operazioni.

Una struttura dati in cui gli elementi vengono estratti nell'ordine inverso rispetto a quello in cui vengono inseriti.

Operazione per inserire un elemento in cima alla pila.

Operazione per estrarre l'elemento in cima alla pila.

Gli algoritmi e le strutture dati sono fortemente legati. Un algoritmo è una soluzione per un problema algoritmico, mentre una struttura dati è un'implementazione concreta di un ADT.

Una coda è un ADT che segue il principio FIFO (First In, First Out). Gli elementi vengono inseriti in coda e rimossi dalla testa.

I linguaggi di programmazione tipati forniscono tipi di dati predefiniti come numeri interi, booleani e caratteri. Ogni tipo di dato ha un set di valori e operatori associati ad esso.

L'operatore + per i numeri interi è definito per addizione. Insieme ai valori 0, 1, 2, ... forma un insieme di regole e procedure che descrivono il comportamento dell'operatore + su quei valori.

L'operatore ¬ per i booleani è definito per la negazione. L'operatore ∧ per i booleani è definito per la congiunzione. Insieme ai valori T, F formano un insieme di regole per il comportamento di questi operatori.

Ogni operatore in un linguaggio di programmazione funziona secondo regole definite, che specificano il comportamento dell'operatore su diversi tipi di dati e valori.

Gli ADT sono strumenti fondamentali per la progettazione e l'implementazione di algoritmi, rendendo il codice più strutturato, leggibile e manutenibile.

Inserire un elemento in coda alla struttura dati.

Estrarre l'elemento in testa alla struttura dati, rimuovendolo.

Restituisce l'elemento che si trova in testa alla struttura dati, senza rimuoverlo

Nel processo di gestione di una coda, l'elemento inserito per primo è 3 e viene inserito nella coda.

Nel processo di gestione di una coda, l'elemento inserito per primo è 5 e viene inserito nella coda.

Nel processo di gestione di una coda, l'elemento inserito per primo è 9 e viene inserito nella coda.

Nel processo di gestione di una coda, l'elemento in testa alla coda viene rimosso.

Se l'elemento da estrarre da una coda è nella prima posizione (head), l'operazione dequeue richiede di spostare tutti gli altri elementi della coda. Questo comporta una complessità temporale di O(N), dove N è il numero di elementi nella coda.

Se l'elemento da estrarre da una coda è nell'ultima posizione (tail), l'operazione dequeue richiede di spostare tutti gli elementi presenti prima dell'elemento da estrarre. Questo comporta una complessità temporale di O(N), dove N è il numero di elementi nella coda.

Nell'implementazione di una coda con array, è possibile simulare un'operazione di enqueue inserendo l'elemento in una posizione successiva rispetto all'ultimo elemento inserito e aggiornando la posizione di tail.

Nell'implementazione di una coda con array, è possibile simulare un'operazione di dequeue estraendo l'elemento all'inizio della coda (head) e aggiornando la posizione di head.

Nell'implementazione di una coda con array, è possibile simulare un comportamento ciclico con head e tail che 'avvolgono' l'array. Ad esempio, se tail arriva alla fine dell'array, la prossima posizione sarà il primo elemento dell'array.

Nell'implementazione di una coda con array, è necessario tenere traccia di dove si trova l'inizio (head) e la fine (tail) della coda. Questo permette di simulare la struttura della coda.

Restituisce la dimensione della coda Q. Se la coda è un array circolare, la dimensione è calcolata considerando il posizionamento della testa e della coda, il modulo della dimensione massima dell'array (Q.M) e l'ovvio problema di overflow (l'array non può contenere più elementi).

Restituisce l'indice successivo nella coda. Se si raggiunge il limite massimo dell'array (Q.M), l'indice viene riavvolto al primo elemento.

Inserisci un nuovo elemento (t) nella coda Q. Se la coda è piena (Q.M - 1), restituisce un errore di overflow.

Restituisce l'elemento in testa alla coda Q senza rimuoverlo. Se la coda è vuota, restituisce un errore di underflow.

Rimuove l'elemento in testa alla coda Q e lo restituisce. Se la coda è vuota, restituisce un errore di underflow.

Implementare una coda utilizzando una lista anziché un array:

Le code possono essere implementate con array e liste, offrendo vantaggi e svantaggi a seconda del contesto.