C++ - Fonction Stack Pop() avec une seule liste chaînée

Question

Pour les débutants, ceci fait partie de mon devoir actuel pour ma classe Structures de données. Je ne demande pas de réponses, je demande de l'aide.

J'ai une classe de pile qui implémente une liste liée au lieu d'un tableau. J'essaie actuellement d'écrire ma fonction pop(). J'ai un noeud pour ma partie backBack de la pile.

Je suis juste confus quant à arriver au prédécesseur de mon nœud theBack.

Toute aide avec ce serait génial! Merci!

Answer 1

Une pile est en réalité raisonnablement simple à mettre en œuvre en tant que liste à liaison unique, en raison de ses opérations de poussée et de bruit restreintes. C'est en fait beaucoup plus facile si vous insérez des éléments poussés à la tête de la liste. Comme c'est le devoir, je fournirai du pseudo-code.

Pour initialiser une pile, il est tout simplement la création:

top -> null 

avec ce code:

def init (stk): 
    stk->top = null     # just initialise to empty. 

Pousser un élément est-il insérait en fait au début de la liste. Donc, lorsque vous appuyez sur 3, 4 et 5, vous obtenez:

 +---+ 
top -> | 3 | -> null 
     +---+ 
     +---+ +---+ 
top -> | 4 | -> | 3 | -> null 
     +---+ +---+ 
     +---+ +---+ +---+ 
top -> | 5 | -> | 4 | -> | 3 | -> null 
     +---+ +---+ +---+ 

avec le code suivant:

def push (stk, val): 
    item = new node      # Create the node. 
    item->value = val     # Insert value. 
    item->next = stk->top    # Point it at current top. 
    stk->top = item      # Change top pointer to point to it. 

Et popping est alors simplement que le premier noeud retirez.

def pop (stk): 
    if stk->top == null:    # Catch stack empty error. 
     abort with "stack empty" 
    first = stk->top     # Save it for freeing. 
    val = first->value     # Get the value from the top. 
    stk->top = first->next    # Set top to the top's next. 
    free first       # Release the memory. 
    return val       # Return the value. 

Answer 2

si vous implémentez une pile, vous voulez pop le nœud supérieur de toute façon, de sorte que vous définiriez thetop être le nœud suivant dans la ligne (qui devrait être un pointeur dans thetop noeud)

Answer 3

Chaque nœud dans la liste des liens simples liés au nœud précédent. Le tout premier objet poussé sur la pile a une valeur nulle, tous les autres pointent vers l'élément 'en dessous' d'eux (le prédécesseur) dans la pile. Donc, avant de détruire le nœud supérieur, vous récupérez le backlink et le sauvegardez en tant que nouveau sommet. Quelque chose comme ce pseudo-code, ce qui suppose une pile de valeurs int:

pop() 
    ALink *poppedLink = myTop; 
    myTop = poppedLink.nextNode; // point to next node 

    int returnValue = poppedLink.value; // save the value 
    delete poppedLink; // destroy the instance 

    return returnValue; 

Si par « prédécesseur », vous voulez dire: « la chose qui a été sauté avant cette »: C'est révolue depuis longtemps, est-ce pas?

Answer 4

Que voulez-vous dire par le "prédécesseur" du top? Le nœud supérieur est la tête de votre liste, il n'a aucun prédécesseur.