We will be extending our sll2 project in dll1 with the addition of doubly-linked lists, as well as the implementation of the queue data structure (using a doubly linked list). You are also to enhance/rewrite/reimplement all existing code based on a singly linked list (node, list, and stack) to make effective use of the doubly linked list.

For this project, you'll update your sll2 project to gain access to the new upgrade-dll1 option in the Makefile:

Change to wherever you copied your code (I'm assuming ~/src/data/sll2 in my example):

lab46:~$ cd src/data/sll2
lab46:~/src/data/sll2$ 

lab46:~/src/data/sll2$ make update
...

lab46:~/src/data/sll2$ make upgrade-dll1
...

lab46:~/src/data/sll2$ cd ../dll1
lab46:~/src/data/dll1$ 

This project codebase is largely identical to the sll2 codebase; it merely adds the new files for the doubly linked list and queue functionality. Be sure to check for new files in the following directories:

• inc - queue.h header and updated node.h header
• src/queue - source code for the queue operations
• testing - queuetest.c file (should work as well as the most recent stacktest)

Queues are frequently considered a peer to the stack data structure, in that the two share many common traits (an underlying linked list) but differ in the restrictions placed upon accessing the linked list.

It works on a principle of “first-in, first-out” (FIFO), which makes it great to use as a buffer for information (order is preserved).

Everyone has real-life experience with a queue… every time you have waited in line somewhere; the grocery store, the bank, midnight release of Super Mario Bros. 2… you “enqueue” yourself at the back of the line, and wait- people are dequeued from the front of the line. Eventually, you will get to the front of the line, and when it is your turn, you dequeue.

So, with a queue, we only add to the back, and take off from the front. No other aspect of the linked list is modified or accessed under the guise of a queue. This restriction of access creates new possibilities for algorithms, enabling useful functionality.

The basic queue operations are: enqueue() and dequeue() which will call the necessary underlying list operations (likely append() and getNode()) while maintaining the back and front pointers (reflecting some pointer in the underlying list, perhaps start and end).

The queue has a buffer variable, which unlike the list's qty (that keeps track of how many nodes are in the list at any given time), buffer mandates a maximum size a queue can be (if the qty has reached buffer, no new nodes should be added (i.e. enqueue()ed)- this is what is known as a buffer overrun condition)). For purposes of flexibility, a buffer of zero denotes an unbounded queue (it can grow indefinitely, just like a list).

To further test your understanding, you are to implement the queue's mkqueue() function this time around.

• Update 1: The issue with stacktest.c would also exist in queuetest.c, so any changes to that need to be forward ported. This has been done.
• An attempt to standardize replaced files has been started- any replaced files will be renamed with a .rev-PREVIOUSREV extension. So going from rev 0 to rev 1, should now end with .rev-0

To successfully complete this project, the following criteria must be met:

• All code must compile cleanly (no warnings or errors)
• Code must be nicely and consistently indented (you may use the indent tool)
• Code must be commented
• Resulting libraries must be operational and functionally correct
  • stack functions must operate as described, conforming to provided function prototypes
  • code must make use of the other node/list functions as appropriate- do not reinvent the wheel
  • evaluations of libraries using various unit tests will be an assessment criteria
• Track/version the source code in a repository
• Submit a copy of your source code to me using the submit tool (or make submit).

To submit this program to me using the base Makefile, run the following command at your lab46 prompt:

lab46:~/src/data/dll1$ make submit
...
Submitting data project "dll1":
    -> dll1-20140412-14.tar.gz(OK)

SUCCESSFULLY SUBMITTED

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.

To submit the project, you will need to create an archive and submit that using the submit tool:

lab46:~/src/data/dll1$ make save
... make save now issues a pre-emptive make clean ...
Archiving the project ...
Compressing the archive ...
Setting permissions ...
lab46:~/src/data/dll1$ cd ..
lab46:~/src/data$ ls dll1*gz
dll2-20140412-14.tar.gz
lab46:~/src/data$