A Linked Stack Example

Try This!
  • Add a dup, a count, and an add function to the stack library to duplicate the top element of the stack, return a count of the number of elements in the stack, and add the top two elements in the stack.
  • Build a driver program and a makefile, and compile the stack library with the driver to make sure it works.

A good example of dynamic data structures is a simple stack library, one that uses a dynamic list and includes functions to init, clear, push, and pop. The library's header file looks like this: 

/* Stack Library - This library offers the
   minimal stack operations for a
   stack of integers (easily changeable) */

typedef int stack_data;

extern void stack_init();
/* Initializes this library.
   Call first before calling anything. */

extern void stack_clear();
/* Clears the stack of all entries. */

extern int stack_empty();
/* Returns 1 if the stack is empty, 0 otherwise. */

extern void stack_push(stack_data d);
/* Pushes the value d onto the stack. */

extern stack_data stack_pop();
/* Returns the top element of the stack,
   and removes that element.
   Returns garbage if the stack is empty. */

The library's code file follows: 

#include "stack.h"
#include <stdio.h>

/* Stack Library - This library offers the
   minimal stack operations for a stack of integers */

struct stack_rec
{
    stack_data data;
    struct stack_rec *next;
};

struct stack_rec *top=NULL;

void stack_init()
/* Initializes this library.
   Call before calling anything else. */
{
    top=NULL;
}

void stack_clear()
/* Clears the stack of all entries. */
{
    stack_data x;

    while (!stack_empty())
    x=stack_pop();
}

int stack_empty()
/* Returns 1 if the stack is empty, 0 otherwise. */
{
    if (top==NULL)
        return(1);
    else
        return(0);
}

void stack_push(stack_data d)
/* Pushes the value d onto the stack. */
{
    struct stack_rec *temp;
    temp=
  (struct stack_rec *)malloc(sizeof(struct stack_rec));
    temp->data=d;
    temp->next=top;
    top=temp;
}

stack_data stack_pop()
/* Returns the top element of the stack,
   and removes that element.
   Returns garbage if the stack is empty. */
{
    struct stack_rec *temp;
    stack_data d=0;
    if (top!=NULL)
    {
        d=top->data;
        temp=top;
        top=top->next;
        free(temp);
    }
    return(d);
}
C Errors to Avoid
  • Forgetting to include parentheses when you reference a record, as in (*p).i above
  • Failing to dispose of any block you allocate - For example, you should not say top=NULL in the stack function, because that action orphans blocks that need to be disposed.
  • Forgetting to include stdio.h with any pointer operations so that you have access to NULL.

Note how this library practices information hiding: Someone who can see only the header file cannot tell if the stack is implemented with arrays, pointers, files, or in some other way. Note also that C uses NULL. NULL is defined in stdio.h, so you will almost always have to include stdio.h when you use pointers. NULL is the same as zero.