[C++] Implementare "push" e "pop"

[HolyFather]

Ciao ho un esercizio di strutture dati da proporvi :

Implementare le funzioni PUSH e POP di uno stack realizzato con due code. Analizzare i tempi di esecuzione
delle operazioni sullo stack.

Soluzione: Implementare uno stack basato su due code significa simulare una politica di accesso LIFO con
strutture dati ad accesso FIFO. Per fare ciò è possibile modificare la funzione Pop perché travasi tutti i valori
(tranne l’ultimo) nell’altra coda e infine ritorni l’ultimo valore. La funzione PUSH invece deve solamente
aggiungere l’elemento nella coda che contiene gli altri, per mantenere lo stesso ordine.

PUSH(S, x)
1 if QUEUE-EMPTY(Q1[S])
2 then ENQUEUE(Q2[S], x)
3 else ENQUEUE(Q1[S], x)

POP(S, x)
1 if QUEUE-EMPTY(Q2[S])
2 then dst←Q2[S]
3 src←Q1[S]
4 else dst←Q1[S]
5 src←Q2[S]
6 ►dst è la coda vuota nella quale verranno travasati i dati
7 while tail[src] - head[src] > 1 ►non è necessario calcolare il modulo
perché la coda è sempre piena dall’inizio e non si verificano cicli
8 do ENQUEUE(dst, DEQUEUE(src)


QUEUE-EMPTY (Q)
1 return head[Q] = tail[Q]
9 return DEQUEUE(src)


IL mio unico problema è questo ; ad esempio prendendo la riga 1
1 if QUEUE-EMPTY(Q1[S])

Non riesco a capire perchè alla coda gli viene dato in pasto lo Stack , che senso ha ??

grazie a chiunque possa aiutarmi ciaoo

[ramy89]

Neanche io ho capito bene
Forse le due liste servono per salvare i dati e fare l' ordinamento,ma non sono sicuro.
Se ho una lista di elementi e li voglio ordinare,cancellandone alcuni,in questo caso avrei bisogno di creare una nuova lista.
Anche io non ho capito,potrebbe essere così:

typedef struct
{
    char *nome;
    char *cognome;
    int eta;
    bool save;
}studente;

Praticamente quando hai la pila di elementi potrebbe essere necessario cancellarne alcuni,il bool può essere utilizzato per decidere se l' elemento va salvato o no.
Si fa il sorting e si elminano gli elementi col bool falso.
E' questo un possibile problema?

Secondo me è sbagliato usare tutte queste definizioni,i prof dovrebbero solo dare il problema generale e poi ognuno lo risolve come vuole,così anche io non capisco la consegna

[HolyFather]

Originariamente inviato da ramy89
Neanche io ho capito bene
Forse le due liste servono per salvare i dati e fare l' ordinamento,ma non sono sicuro.
Se ho una lista di elementi e li voglio ordinare,cancellandone alcuni,in questo caso avrei bisogno di creare una nuova lista.
Anche io non ho capito,potrebbe essere così:

typedef struct
{
    char *nome;
    char *cognome;
    int eta;
    bool save;
}studente;

Praticamente quando hai la pila di elementi potrebbe essere necessario cancellarne alcuni,il bool può essere utilizzato per decidere se l' elemento va salvato o no.
Si fa il sorting e si elminano gli elementi col bool falso.
E' questo un possibile problema?

Secondo me è sbagliato usare tutte queste definizioni,i prof dovrebbero solo dare il problema generale e poi ognuno lo risolve come vuole,così anche io non capisco la consegna

Una coda è tipo un array , che ha una filosofia FirstInFirstOut (FIFO )

ad esempio tu hai un array Q con 6 posizioni e sono inseriti prima l'elemento 5 e poi l'elemento 7
1 2 3 4 5 6
5 7

Metti che in posizione uno hai messo il primo elemento che è 5 , poi il secondo 7 .
Ci sono degli indici particolari , head[Q] che è la testa che nell'esempio è l'elemento in posizione uno ed è da dove vengono tolti gli elementi dalla coda, e tail[Q] che è la coda , ovvero dove andrai a inserire il nuovo elemento ( in questo caso un nuovo eventuale elemento verrà inserito in posizione 3 )

ad esempio se chiamo la funzione togliElemento(Q) , la funzione eliminerà l'elemento in posizione 1 , dandomi questo risultato , ( la nuova head[Q] sarà la posizione 2 )

1   2    3 4 5 6
     7

se invece invocherò la funzione aggiungiElemento(Q,8), l'elemento verrà aggiunto in posizione 3 ( ovvero dove è tail[Q] e il nuovo tali[Q] sarà tail[Q]+1 cioè 4)

1   2    3    4 5 6
     7    8

( perdon ma non riesco ad allinarli )

Come vedi qui c'è una politica di tipo primo elemento inserito , primo elemento che viene tolto.

Nello stack invece è la classica pila , ovvero tu inserisci gli elementi nella pila e se vuoi togliere devi togliere l'ultimo elemento che hai inserito ( Last in First out LIFO )

esempio PUSH(S,1) , PUSH(S,2) , PUSH(S,3)

3
2
1

Se vuoi estrarre un valore POP(S)

2
1


IL problema ti chiede di implementare la coda utilizzando due stack , ovvero realizzare la filosofia FIFO utilizzando opportunamente la filosofia LIFO dei due stack

[ramy89]

Posso provare,se ho capito bene la coda è come un nastro che slitta,lo stack è fisso.
provo a scrivere una cosa del genere:

typedef struct
{
    char *nome;
    char *cognome;
}lista;

In pratica per aggiungere un elemento alla coda non ci dovrebbero essere problemi,perchè basta aggiungerlo alla coda.
Il problema è cancellare un elemento,perchè devi fare slittare tutti gli altri,ecco perchè dice di utilizzare due stack.
Quando implemento le pile io in genere tengo il puntatore al numero di strutture anzichè il puntatore al prossimo elemento.
Ecco come ho provato a farlo:

lista *cancella elemento(lista *pointer_1, *num)
{                                                                               // la lista è già allocata in memoria
    lista *pointer_2=(lista*)calloc((*num)-1,sizeof(lista));       // alloco una struttura destinata
    int i,j=*num-1;                                                            // a conetenere la nuova lista
    for(i=0;i<j;i++,j--)
    {
        copia(pointer_2[i],pointer_1[j]);                            //funzione per copiare 
    }                                                                         // il secondo elemento nel primo
// una volta copiate se non erro dovresti avere la struttura nell' ordine inverso,
//tranne l' elemento uscente,cioè pointer_1[0] che va eliminato
    free(pointer);                        // la struttura vecchia va eliminata
    for(i=0,j=*num-1;i<j;i++,j--)
    {
        swap(pointer_2[i],pointer_2[j];                        // la swap scambia due strutture
    }
    return pointer_2;

A questo punto se ho fatto tutto correttamente dovresti avere la stessa identica struttura ma slittata di una posizione,e hai tolto l' elemento che era pointer_1[0] che era da cancellare.
Funzioni come copia e swap poi sarebbero facili da implementare.
Occhio che non ho provato a compilarlo,fammi sapere se è giusto poi.