Lab46 Wiki

Queues, similar to stacks, are defined as linear data structures. However, opposite to a stack, a queue is open on both ends, data joins the list of data at the back of the queue, and leaves the list from the front of the queue. This principle is called FIFO, First In First Out.

Think of it as the line of the grocery market when you're ready to be cashed out. The person currently paying for their groceries with the cashier is at the front of the queue, and as soon as they're done paying they will be the first to leave the queue. You on the other hand, since you are the last will to join the queue at the back of the line, will therefore be last to leave the queue.

You will find a new header file contained in the inc directory called queue.h.

The new queue struct has the following properties:

• Node *front - Same as data→lead
• Node *back - Same as data→last
• List *data - Pointer to list holding actual queue data
• ulli buffer - Maximum length of queue (0 = infinite)

For this project you will be working with 6 new functions related to the new queue struct.

• mkqueue() - Allocates a new queue with an empty list.
• purge() - Empties & removes the data list from a queue.
• rm() - Empties, deallocates, and nullifies a queue.
• cp() - Copies one queue to another.
• dequeue() - Grabs a node off of the front of a queue.
• enqueue() - Places a node on the back of a queue.

Although not specified inside of the functions, the return codes should stack upon each other. So while they list a bunch of DLQ codes, the unit test will specify what return codes should be returned. The ones specified in the unit test include node return codes along with list return codes depending on what is happening.

Queues are composed of lists, so make sure to reuse functions you have previously made from the previous weeks. You can use your stack functions as a reference, and make some tweaking, by doing this not only will it make your life significantly easier, but it will also shorten the amount of time it takes for this project. There is absolutely no need to remake everything you need to do from scratch. Also, you can make use of the make command -make use-test-reference. This uses a working implementation of object files from the previous dllX projects, and can very much help you if your previous projects did not pass all unit tests.

Output is strictly modifications to the queue, the associated list, and the front and back nodes. Nothing to stdout aside for testing purposes.

Unit tests ran the same way, make clean, make, and make check to get a general view of all tests. Run each specific unit test inside of bin/ to see what is happening in each specific test. Run the verify-(corresponding test) to see a general view of the specific test, this one displays matches and mismatches without output.