[C] Regole per implementazione di pile e code

[ramy89]

Una pila segue la politica last in first out, cioè l' ultimo aggiunto è l' ultimo ad essere estratto.
Mentre nella coda si estrae il primo elemento aggiunto in ordine cronologico.
Ma quello che non è capito è qual'è la posizione degli elementi aggiunti ed estratti.
Seguendo questa politica potrei implementare una pila in questi due modi:
-Aggiungo gli elementi in prima posizione e estraggo sempre quelli in prima posizione;
-Aggiungo gli elementi in ultima posizione e estraggo quelli in ultima posizione.
Con le code:
-Aggiungo gli elementi in prima posizione e estraggo quelli in ultima posizione;
-Aggiungo gli elementi in ultima posizione e estraggo quelli in prima posizione.

Quale dei due modi è corretto?

[serioja90]

-Pile:
I modi da te proposti sono tutti corretti, però per la realizzazione della pila ti consiglierei il primo, perché sia l'inserimento, che l'estrazione degli elementi sarà più semplice e veloce.
Adottando il secondo modo dovresti usare un puntatore all'ultimo elemento per l'aggiunta di elementi e dovresti scorrere l'intera pila ogni volta che dovrai eliminare un elemento.

-Code:
Per quanto riguarda le code, direi che il secondo modo è quello migliore, perché basta avere un puntatore che punta all'ultimo elemento per poter inserire uno nuovo, mentre per eliminare il primo è sufficiente impostare il secondo elemento come primo.
Se adotti il primo modo, ogni volta che dovrai estrarre un elemento sarà necessario scorrere l'intera coda.

[ramy89]

Originariamente inviato da serioja90
Se adotti il primo modo, ogni volta che dovrai estrarre un elemento sarà necessario scorrere l'intera coda.

Anche qua potrei avere un puntatore all' ultimo elemento.
Ma il problema non sorge perchè io uso liste bidirezionali.
Volevo sapere quale metodo è concettualemtne più corretto.
Cioè se ho una pila e ci aggiungo un elemento, e ho un vettore che è la linearizzazione di quella pila, in che posizione si trova l' elemento che ho aggiunto?

[serioja90]

Non credo che faccia alcuna differenza il posto dove verrà aggiunto l'ultimo elemento, basta che sia primo ad essere estratto. Per cui puoi utilizzare sia il primo che il secondo modo.
La realizzazione della struttura dati può essere qualsiasi, potresti inventarti anche un nuovo modo per crearla, ma la cosa più importante è che sia conforme al concetto di tale struttura
e che sia il più produttiva possibile.

[MItaly]

Non c'è un modo "giusto" a prescindere.
Il metodo più conveniente dipende dal tipo di struttura dati che ci sta sotto: se usi una lista linkata conviene aggiungere e togliere elementi all'inizio (in modo da non doverla scorrere tutte le volte), oppure è indifferente se ti tieni pronto un puntatore all'ultimo elemento (cosa che sarà utile nel caso della queue); se invece usi un array (per la pila) ovviamente conviene aggiungere e togliere in fondo, dato che aggiungere elementi all'inizio vuol dire spostare tutto avanti di un posto ogni volta.

[ramy89]

Ok, c'è un' altra cosa che voglio sapere.
Io una lista l' ho provata a fare con un puntatore a void che contiene l' informazione, più un campo che contiene il numero di byte da leggere.
Così ci posso mettere dentro qualsiasi tipo di dato, anche elementi eterogenei, premesso che una volta estratti so come leggerli e so convertirli.
Ma questo può essere considerato C standard? E' conforme alle iso99? E' concettualmente corretto?

[MItaly]

Originariamente inviato da ramy89
Ok, c'è un' altra cosa che voglio sapere.
Io una lista l' ho provata a fare con un puntatore a void che contiene l' informazione, più un campo che contiene il numero di byte da leggere.
Così ci posso mettere dentro qualsiasi tipo di dato, anche elementi eterogenei, premesso che una volta estratti so come leggerli e so convertirli.
Ma questo può essere considerato C standard? E' conforme alle iso99? E' concettualmente corretto?

Sì
Sì (§6.3.2.3 - "A pointer to void may be converted to or from a pointer to any incomplete or object type. A pointer to any incomplete or object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.")
Sì (ed è l'unico modo di avere container generici in C)