[C] Aiuto su stack mediante liste

[Manugal]

Ho bisogno di aiuto riguardo le operazioni di push e pop che non ho molto capito.

void push(data d, stack *stk){

elem *p;
p=malloc(sizeof(elem));
p->d=d;
p->next=stk->top;
stk->top=p;
stk->cnt++;
}

data pop(stack *stk){

data d;
elem *p;

d=stk->top->d;
p=stk->top;
stk->top=stk->top->next;
stk->cnt--;
free(p);
return d;
}

In entrambe non riesco a capire perché p deve andare a puntare stk->top e stk->top deve andare a puntare p; che stk->top deve puntare a p forse l'ho capito (dato che p viene posto in cima alla lista). Ma perché anche il contrario? Grazie.

[Brazorv]

posta le strutture stack e elem
ps: usa il tag [C0DE] [/C0DE] (con la o al posto dello 0) per inserire il codice

[Manugal]

 

struct elem{
  data d;
  struct elem *next;
};

typedef struct elem elem;

struct stack{
   int cnt;
   elem *top;
};

typedef struct stack stack;

Ecco come sono definite.

[Brazorv]

Per implementare uno stack con le liste concatenate il metodo più semplice è quello di inserire e togliere gli elementi all'inizio della lista.
Se tu hai questa lista:

stk->cnt = 3
  stk->top
         |
         v
         primo->next -----> secondo->next -----> terzo->next=NULL

quando inserisci un nuovo elemento p,lo devi inserire come primo elemento della lista, perciò p->next dovrà puntare al primo elemento della lista:
p->next=stk->top; // stk->top punta al primo elemento della lista
poi stk->top dovrà puntare al primo elemento della lista aggiornata, che ora è p:
stk->top=p;
dopo l'inserimento avrai questa situazione:

stk->cnt = 4
  stk->top
         |
         v
         p->next -----> primo->next -----> secondo->next -----> terzo->next=NULL

[Manugal]

Grazie mille ora ho capito