Table of Contents

Corning Community College

CSCS2320 Data Structures

PROJECT: Lists - Doubly-Linked Queues (DLQ0)

OBJECTIVE

Onto Queues! Another very commonly used data structure, we will be building it atop our list.

Don't forget to contribute to project documentation! That helps to ensure everyone is invested in the project.

OVERVIEW

Our queue, like our stack, will in many ways be a restricted-access list: access with the queue functions will only manipulate the list at certain points, creating a consistency we don't have with full-access lists.

Queues are a First In, Last Out structure (or Last In, First Out), and understanding the value that provides is key to effectively leveraging this data structure.

UPGRADING

To assist with consistency across all implementations, project files for use with this project, along with the integration of the work you did on the last project, is made possible via a special recipe in the Makefile.

Simply go into the project base directory, and run: 

lab46:~/src/SEMESTER/DESIG/prevPROJECT$ make upgrade-dlq0

EDIT

You will want to go here to edit and fill in the various sections of the document:

BACKGROUND

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.

SPECIFICATIONS

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.

PROGRAM

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 SPECIFICATIONS

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

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.

 

SUBMISSION

To be successful in this project, the following criteria (or their equivalent) must be met:

Submit Tool Usage

Let's say you have completed work on the project, and are ready to submit, you would do the following: 

lab46:~/src/SEMESTER/DESIG/PROJECT$ make submit

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.

RUBRIC

I'll be evaluating the project based on the following criteria: 

91:dlq0:final tally of results (91/91)
*:dlq0:obtained project by the Sunday prior to duedate [6/6]
*:dlq0:clean compile, no compiler messages [13/13]
*:dlq0:implementation passes unit tests [13/13]
*:dlq0:adequate modifications to code from template [26/26]
*:dlq0:program operations conform to project specifications [26/26]
*:dlq0:code tracked in lab46 semester repo [7/7]

Pertaining to the collaborative authoring of project documentation

Additionally