CPSC 241-002 Computer Science IV
(Data Structures and Algorithms)
Fall 1998
TTh 12:30--1:45 Daniel 408
Assignment 5
<http://andrewd.ces.clemson.edu/courses/cpsc241/fall98/hw/asg5.html>

Objectives:
To implement the stack data structure using the queue data structure. This assignment is similar to one of your labs, however, here you are creating and using your own doubly-linked list, and stack classes. You can think of the stack data structure as being conceptually layered on top of the queue data structure, thus removing the user from the ``low level'' queue implementation by one level of abstraction. You are in a sense creating an application program interface (or API) to your queue class.

Due date:
10/08/98

Description:
  1. Using the doubly-linked circular QNode class defined earlier (oll1.cpp), reuse relevant portions of the code to provide a generic queue node class which can act as the queue head or as a list node.

    The idea here is to use the QNode in such a way so that while the node itself is attached to a list, via its forward and back pointers, it also uses a ``user pointer'' to point to an arbitrary object. That is, the QNode's user pointer is pointing to void, or simply a void pointer.

    The user pointer must be initialized to point to the object passed to the node constructor as an argument.

    Provide the following member functions for the QNode class:

    • fadd()
    • eadd()
    • fdel()
    • edel()
    • fnext()
    • lprev()
    • uptr()
    These are similar to the previous routines that were specified by the QHead class. Note the new uptr() member function. This member function returns the user void pointer. Note also that the forward and backward print routines are no longer part of the QNode class. They've been removed due to the fact that a QNode object has no way of ``knowing'' what is being stored in the user data and thus it cannot not be expected to print or even access this data. This functionality has been relegated to whatever user class is using the QNode class for linked list storage.

    Your code should be arranged so that the QNode class interface is in separate header (.h) file, while the class interface is in a .c file.

  2. Create a new Stack class which will use the QNode class to store its objects on the queue's doubly linked list. The Stack class uses the QNode class for this purpose via object composition. That is, it simply has a QNode* (pointer to QNode) private data member. Include also an integer private data member to store the stack integer values.

    Provide the following stack operations:

    • data()
    • push()
    • top()
    • pop()
    • fprint()

    Hints:

    • You will need a stack head node whose QNode* private data member is, by extension, used as the queue head node.
    • The stack routines are rather simple in that they just use the queue node member functions.
    • You might find these operations a little ``tricky'':
      • the proper use of the stack's QNode* private data member, especially being aware when the queue node pointer is being used as the queue head (in the stack implementation you can assume that this pointer points to the stack head),
      • access to the stack data via the queue class's use of the uptr() user data access routine (here, since uptr() returns a pointer to void, you'll need to cast the void pointer to a stack node pointer).

    Your code should be arranged so that the Stack class interface is in separate header (.h) file, while the class interface is in a .c file.

  3. Write a program to exercise the Stack class by creating a user-specified sized stack of integers. This is similar to the doubly linked list program, except that now you're using the Stack class to indirectly create a doubly linked list.

    Your code should be arranged so that the main() routine is in a separate .c file. Use a Makefile to compile all the modules.

    Here's the sample output: 

    stack should be empty: stack is empty
Enter stack size: 5
printing forwards:
4
3
2
1
0
getting top node:
4
removing from front:
4
3
2
1
0
stack should be empty: stack is empty
    Warning: while the output of this program may seem somewhat mundane, its conceptualization and proper implementation may not be. Start early! First understand the specifications of the problem and then design the proper data structures and their usage.

    What to hand in:
    ``Professional-quality'' writeup, including:
    1. Cover page containing:
      Course Id--Section No.
      Name:
      SS No:
      Assignment No.
    2. Assignment description
    3. Solution description (e.g., program design, description of algorithm, etc., however appropriate).
    4. Lessons learned, identified interesting features of your program
    5. Appendix A: Source code listing
    6. Appendix B: Sample input (if any)
    7. Appendix C: Sample output
    The entire document should be a clearly written account of what you were to accomplish, what you in fact did accomplish, and what you learned (how you accomplished it). The code and sample runs, listed in the appendices, should be clearly documented (e.g., document the source code, generate informative output).

    The general presentation of your document counts! (This includes qualities such as neatness, formatting, and legibility.)