List-Based Queues

Summary: This laboratory exercise introduces the concept of the queue abstract data type and provides experience implementing this ADT with a linked list.

List-Based Queue ADT

In this lab, we will focus on queues of strings, and this leads to the following declarations:

typedef struct node {
  char * data;
  struct node * next;
} queueNode;

typedef struct {
  queueNode * head;
  queueNode * tail;
} stringQueue;

With this framework, the signatures for the various queue operations are the same as with array-based queues.

Exercises

  1. Copy the header and library file you wrote for the previous lab on queues with arrays, calling them listQueue.h and listQueue.c. Modify them so that the queues are implemented by linked lists. In doing so, you will need to
    • Update the symbol used in the include guard to reflect the new file name
    • replace the previous struct and #define, and also add the new queueNode structure.
    • change the bodies of the six core prototype functions
    • Add a new rule and target to your Makefile to compile the new file to an object.
  2. Copy your previous test driver to testListQueue.c and change your #include to the list-based queue header.
    • The declaration of the stack variables for your testing queues does not need to change and you should not have to change any of the code used for testing.
    • As before, add two more Makefile targets (one to compile, one to link). Build and run your new program. The output of should be identical in all respects to the output of the program from the previous section.
  3. The enqueue operation allocates space for a new node and copies the string item into that node. The dequeue could return a pointer to the character array within the node or it could copy the string back to a newly created array before passing back a reference. Is there an advantage of one of these approaches over the other? Explain.

    Note: In either case, dequeue must deallocate space for the node that is removed.

  4. Write a print function that prints all elements on a queue, from the head of the queue to its tail. (This function can be helpful in testing.)

  5. If this lab is to be handed in for credit, print out the code you wrote for steps 1 through 4, including your Makefile.

  6. Frequently we wish to clear the contents of a data structure like a queue.
    1. Implement the following function to remove all the nodes from the queue.
      void
      clear (stringQueue * queue);
    2. Write tests to verify your clear procedure seems to function properly.
  7. Run AddressSanitizer over your test program to verify it does not have any memory problems. Eliminate any it finds.

For those with extra time

  1. Test your programs carefully.
    1. Think of a set of test cases that will thoroughly test your program. What test cases should you include?

      It is troublesome, but true, that there is as much art as science in testing programs well, given that one goal of testing is to think of unusual occurrences that may not come readily to mind. In some cases, it is helpful to have a friend try to run your program, given minimal instruction, and see what they will try to do. You might be surprised at the results!!

      At the very least, be sure that your cases include an example of each response required by the problem specification. (For example, you should consider when error conditions should arise, and your testing should include those cases—does the program handle these cases appropriately?) You should also pay particular attention to "boundary cases" that may arise: in the context of queues, reasonable candidates for boundary cases might include adding or deleting items from queues with 0, 1, or perhaps more items.

    2. Note that programs for queues could be written to accept input repeatedly from the user. To "automate" such a user, enter your test data in a file with one input value per line, so that the newline character in the file simulates the user pressing the enter key. You do not need to type ctrl+d into your test data file to indicate the end of the file: just end the file, and your program will correctly detect when it reaches the end of the file.

      Build such program and run it, redirecting to get its input from the test data file. For example, your run command might look like this:

      ./queue-test < queue-test.data

      Obviously, you will want to examine your output for correctness.

      Your output from running the program this way may look strange because the input prompts appear, but the user input does not. Depending on the situation, you may want to comment the prompts out of your code, or you may want to just put up with odd looking output.

      The value of testing C programs in this way is that it allows you to use the same test cases multiple times without retyping them. Why is this useful? Consider the possibility that the first time you test a given case, your program gives an incorrect response. Once you fix the problem, you will want to test it again, and you will want to be sure that you have tested it on the same data. Further, you will want to re-test all of your previously working cases to make sure that your most recent change did not cause other cases to fail.

      It is good practice (though a somewhat difficult habit to get started) to maintain a set of test cases for each program you write. This makes it easy to re-test your entire program when a new change is made. Re-running all your test cases for each new change is known as system testing.