PROJECT: DOUBLY LINKED QUEUES (dlq0)

OBJECTIVE

Building on top of your doubly-linked list implementation, implement a queue.

TASK

By the deadline, please do the following:

  • create a Queue management struct, containing a size element, a front Node pointer, a back Node pointer, and a data List pointer
    • size, if 0, will indicate an unbounded queue (positive means bounded)
    • front points to the node at the front of the queue (where nodes leave)
    • back points to the node at the back of the queue (where nodes join)
    • data points to the underlying list the queue is built upon
  • implement an mkqueue() function
  • implement an rmqueue() function
  • implement an enqueue() function
  • implement a dequeue() function

BACKGROUND

A queue is a FIFO (First-In, First-Out) data structure, which we will simplify by building on top of our existing doubly-linked list infrastructure.

The first item placed into the queue will be the first item retrieved from the queue. Think of a line at a store: those who arrive first are served first, and newcomers join at the end of the line.

The strength of the queue comes from the particular restrictions we place on its access: we only add at one end (the back), and we only remove from the other (the front). Nodes in the middle of the queue are not directly accessible. These two ends will correspond to the start and end of your underlying list (your implementation, you pick which end of the list is the front and which is the back, but be consistent, and run with it).

The queue enqueue() function will take the node and place it at the back of the queue (by calling the appropriate underlying list function), adjusting back (and, if the queue was empty, front) accordingly.

The queue dequeue() function will retrieve the node at the front of the queue (by calling the appropriate underlying list function), adjusting front (and, if the queue is now empty, back) to reflect the new state of the queue.

You will want to call upon the underlying list functionality to do the heavy-lifting. The front and back pointers exist to keep the queue's view of its endpoints up to date; the data list pointer is how you reach the list functions that actually manipulate the nodes.

For the queue, ENQUEUE and DEQUEUE are the two central actions. Without them there is no queue.

Be mindful of the following scenarios, as they are common sources of error:

  • enqueueing onto an empty queue (both front and back must be set)
  • dequeueing the last remaining node (both front and back must be cleared)
  • dequeueing from an empty queue (should fail gracefully)
  • enqueueing onto a full (bounded) queue (should fail gracefully)

SUBMISSION

182:dlq0:final tally of results (182/182)
*:dlq0:create queue struct [26/26]
*:dlq0:create and test mkqueue function [26/26]
*:dlq0:create and test rmqueue function [26/26]
*:dlq0:create and test enqueue function [52/52]
*:dlq0:create and test dequeue function [52/52]

Additionally:

  • Solutions not abiding by spirit of project will be subject to a 25% overall deduction
  • Solutions not utilizing descriptive why and how comments will be subject to a 25% overall deduction
  • Solutions not utilizing indentation to promote scope and clarity will be subject to a 25% overall deduction
  • Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction