Solution for StackPush()


StackPush() needs to perform a few steps to push something onto the stack. Let's consider a stack with 2 elements, and look at what needs to be done.

 stackP
   |
   v
--------
|top   |
-----+--
     |
     v
    --------   ---------
    | B | -+-->| A | 0 |
    --------   ---------

Remember, a stack is represented by a stackT, which is a structure that contains only a pointer (named top) to the first node in the list.

Our StackPush() function will receive a pointer to a stackT (call it stackP) since it needs to change the top field. In other words, the stack is passed by reference.

As an example, the steps we need to perform to push on the letter 'C' are:

  1. Allocate a new node:

               stackP
                 |
                 v
              --------
              |top   |
    newNodeP  -----+--
        |          |
        v          v
        --------   --------   ---------
        |   |  |   | B | -+-->| A | 0 |
        --------   --------   ---------
    

    Remember that we'll dynamically allocate nodes at run-time and that malloc() returns a pointer to newly-allocated memory.

  2. Put information in the node:

               stackP
                 |
                 v
              --------
              |top   |
    newNodeP  -----+--
        |          |
        v          v
        --------   --------   ---------
        | C |  |   | B | -+-->| A | 0 |
        --------   --------   ---------
    

    Above, we've put the new element 'C' into the node.

  3. Link the node into the list:

               stackP
                 |
                 v
              --------
              |top   |
    newNodeP  -----+--
        |          |
        v          v
        --------   --------   ---------
        | C | -+-->| B | -+-->| A | 0 |
        --------   --------   ---------
    

    by making the next pointer of the first node point to the old top.

  4. Fix the top:

               stackP
                 |
                 v
              --------
              |top   |
              -----+--
                   |
         +---------+
         v
        --------   --------   ---------
        | C | -+-->| B | -+-->| A | 0 |
        --------   --------   ---------
    

    which requires making the top refer to the new beginning of the list. Here is an implementation for StackPush():

    void StackPush(stackT *stackP, stackElementT element)
    {
      stackNodeT *newNodeP;
    
      /* Allocate a new node to hold information. */
    
      newNodeP = (stackNodeT *)malloc(sizeof(stackNodeT));
    
      if (newNodeP == NULL) {
        fprintf(stderr, "Insufficient Memory to Push Element on Stack.\n");
        exit(1);  /* Exit program, returning error code. */
      }
    
      /* Put information in node. */
    
      newNodeP->element = element;
    
      /* Link new top node to old top node. */
    
      newNodeP->next = stackP->top;
    
      /* Make the new node the top. */
    
      stackP->top = newNodeP;
    }
    
    Note that this code works even when the stack is initially empty, i.e., when the top is NULL.


    Note: In general, you should see if there are different cases that need to be handled when writing operations on linked lists, i.e., "Does the code need to be different when the list is empty, has 1 element, 2 elements, etc.?"

    Now, think about what needs to be done for StackPop().

    Remember, in StackPush(), we dynamically-allocated nodes with malloc(). What then will we do to the node we no longer need in StackPop()?


    BU CAS CS - Solution for StackPush()
    Copyright © 1993-2000 by Robert I. Pitts <rip at bu dot edu>. All Rights Reserved.