The double_stack Library

We've discussed the stack data structure in class. It's an instance of a "LIFO" ("Last In, First Out") structure. In this lab, you'll implement a stack of double precision values using a list where we add and remove elements on the same end of the list. You'll create a library double_stack with a header file and a source file.

The double_stack.h Header File

There are no modifications to make to the header file, so the only thing you need to do is:

1. Download the file double_stack.h to your lab directory.

   Here's what it looks like:

/*
 * This is the external interface of the double_stack library. Note
 * that the stack itself is intentionally not externally visible.
 */

extern int  doubleStack_pop(double *d_p);
/* pops a double value off the stack -- returns 0 or 1 for success or failure */

extern void doubleStack_push(double d);
/* pushes a double value on the stack */

extern void doubleStack_print(void);
/* prints the stack on stdout, but does not alter it */

Study this header file. It declares the only externally-visible parts of the library.

The double_stack.c Library Source File

Like monsterdb, the double_stack library is implemented in a single source file: double_stack.c. Here's what you need to do to build it:

1. Download the template file double_stack_tplt.c to your lab directory.

2. Rename it:

   $ mv double_stack_tplt.c double_stack.c
   

   Here's what it looks like:

#include <stdio.h>
#include <stdlib.h>

#include "double_stack.h"

/*
 * We implement a stack as a list that we always insert and remove the
 * first element of.
 */

struct DoubleStack {
    /*
     * ASSIGNMENT
     *
     * Declare two structure elements:
     *
     * - a pointer `next_p` to the next `struct DoubleStack` in the
     *   list (which is NULL at the end of the list).
     *
     * - a double value `d`
     */
};


/*
 * ASSIGNMENT
 *
 * Declare a pointer `doubleStackBase_p` to the "base" (aka "head") of
 * the `struct DoubleStack` list. This pointer is the only part of the
 * stack that isn't dynamically allocated. Make it hidden outside of
 * this library (hint: "static"). Initialize it to NULL. (According to
 * C syntax, this last step isn't necessary, but it's a nice reminder
 * to the programmer that it's an empty list.)
 */


/*
 * Although it only calls free() now, using a "*_delete()" function is
 * a good idea in case we decide we later need to do something
 * different, like memory "recycling". (In C++, such functions are
 * called "destructors".) This should be the *only* place `struct
 * DoubleStack` pointers are freed.
 */
static void doubleStack_delete(struct DoubleStack *doubleStack_p)
/* deallocate a `struct DoubleStack` node from the heap */
{
    free(doubleStack_p);
}


/*
 * This should be the only place `struct DoubleStack` pointers are
 * allocated storage. Note that it initializes every attribute of the
 * allocated storage. This, too, is a good practice.
 */
static struct DoubleStack *doubleStack_new(double d)
/* allocate and fill in a `struct DoubleStack` node from the heap */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call malloc() to assign a struct DoubleStack pointer `doubleStack_p`
     *  to point to a block of heap memory which is the size of a
     *  struct DoubleStack.
     * set `doubleStack_p`'s `next_p` pointer to NULL
     * set `doubleStack_p`'s `d` attribute to the `d` argument
     *  of this function
     * return `doubleStack_p`
     */
}


void doubleStack_push(double d)
/* see header */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call doubleStack_new() with `d` to create a new list element
     *  `doubleStack_p`
     * set `doubleStack_p`'s struct's `next_p` attribute to `doubleStackBase_p`
     * set `doubleStackBase_p` to `doubleStack_p`
     */
}


int doubleStack_pop(double *d_p)
/* see header */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * if `doubleStackBase_p` is NULL,
     *     return 0 (there's nothing to pop off the stack)
     * set a `struct DoubleStack` pointer `doubleStackTop_p` to
     *  `doubleStackBase_p`
     * assign `doubleStackTop_p`'s `d` attribute to wherever `d_p` is pointing
     * set `doubleStackBase_p` to its struct's `next_p` attribute
     * call doubleStack_delete() on `doubleStackTop_p`
     * return 1 (success)
     */
}

void doubleStack_print(void)
/* see header */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * try to pop the top element off the stack with doubleStack_pop()
     * if successful,
     *     (recursively) call doubleStack_print() to print the rest of
     *      the stack
     *     call printf() to print the `d` attribute of
     *      `doubleStack_p`'s struct on a single line using the "g"
     *      (general) floating point format with a minimum column
     *      width of 20 and (a maximum of) 14 significant digits
     *     call doubleStack_push() to push the top element back on top
     *      of the stack
     *
     * Technically, this prints the stack "upside down", but IMHO that
     * order seems more intuitive to the interactive user.
     */
}

3. Follow the instructions in the comments. The "ASSIGNMENT" comments mark places where you need to make changes.

4. Compile your code to produce double_stack.o:

   $ gcc -Wall -c double_stack.c
   

   You'll use this "object" file in the next part.

The double_stack_test Test Program

The lab directory contains three source files that should all work with double_stack. They are:

1. Download the file double_stack_test.c to your lab directory. Here are its contents:

#include <stdio.h>
#include <stdlib.h>

#include "double_stack.h"


int main(int argc, char *argv[])
{
    double d;

    doubleStack_push(1.0);
    doubleStack_push(34.99);
    doubleStack_push(-4.5);
    doubleStack_push(2.139);
    doubleStack_push(-22.77);
    printf("initial stack:\n\n");
    doubleStack_print();
    if (!doubleStack_pop(&d)) {
        fprintf(stderr, "unexpected error in pop() -- exiting\n");
        exit(1);
    }
    printf("\n");
    printf("after popping \"%f\" off stack:\n\n", d);
    doubleStack_print();
    return 0;
}

2. Do not modify this file, just compile it with:

   $ cc -Wall -c double_stack_test.c
   

3. Link it it together with double_stack.o to build the double_stack_test.exe program (aka "binary"):

   $ cc double_stack_test.o double_stack.o -o double_stack_test.exe
   

4. Run it and make sure it's giving the expected output.

Study this file to understand how double_stack works. You'll use it unchanged to implement your next homework. Note especially how doubleStack_pop() indicates success or failure by its return value and sets the popped value through its pointer argument.

When you have completed this, show and demonstrate your code to the lab assistant and he will sign you out.