Quelle est la différence entre ces deux différentes implémentations de la fonction StackTop?

Question

J'étudie un cours sur les structures de données et actuellement je suis coincé avec quelque chose dans les piles. Dans la mise en œuvre de la fonction StackTop (ce qui en fait une copie ou « retours dans un sens » l'élément supérieur de la pile sans affecter la pile.) Le code ci-dessous est la mise en œuvre de celui-ci et il est clair,

void StackTop(StackEntry *pe, Stack *ps){ 
    *pe=ps->entry[ps->top-1]; 
} 

mais tant que nous voulons donner à l'utilisateur la valeur de l'élément supérieur dans la pile ne pourrions-nous pas faire la fonction comme ceci? Et si oui, quelle est la différence entre ces deux implémentations?

StackEntry StackTop(Stack *ps){ 
    return ps->entry[ps->top-1]; 
} 

Gardez à l'esprit que StackEntry est un type de données défini par l'utilisateur.

Answer 1

L'un ou l'autre peut être utilisé. La principale différence est le nombre de copies effectuées.

Dans le premier cas, la valeur résultante est écrite directement dans la variable cible via un déréférencement de pointeur. Dans le second cas, la valeur est (dans la plupart des implémentations) placée sur la pile, puis copiée dans la variable recevant la valeur de retour, en supposant que la valeur de retour est affectée. Pour le cas de valeur de retour, étant donné qu'une structure est renvoyée, le compilateur ne copie probablement pas la valeur de retour à la pile mais à un autre emplacement et place un pointeur sur cet emplacement sur la pile. Ceci est entièrement à la mise en œuvre cependant. Dans les deux cas, les données de structure sont copiées deux fois. Si la structure est relativement petite, il ne devrait pas y avoir de différence mesurable, bien qu'elle puisse devenir significative si la structure est de plusieurs mégaoctets.

Answer 2

Les deux fonctions n'ont pas de bonne conception. Le problème des deux fonctions est que la pile peut être vide. Dans ce cas, les fonctions ont un comportement indéfini et il est difficile de déterminer si c'est le cas.

En C une meilleure définition de la fonction peut ressembler à

int StackTop(Stack *ps, StackEntry *pe) 
{ 
    int success = ps->top != 0; 

    if (success) 
    { 
     *pe = ps->entry[ps->top-1]; 
    } 

    return success; 
} 

Si vous ne vous préoccupez pas du comportement indéfini des fonctions parce qu'il ya une plus fonction qui indique si la pile est vide, alors vous devriez envisager une plus de mise en œuvre de la fonction qui permettra de changer la valeur stockée dans la pile. Une telle fonction peut ressembler à

StackEntry * StackTop(Stack *ps) 
{ 

    return &ps->entry[ps->top-1]; 
}