Queue - Linked-List Implementation - Functions

Here, besides discussing the queue data structure, we will demonstrate how to use static helper functions.

Review:

Recall, we decided to implement a queue using a linked list. The data types that we created for the queue where organized (in the queue module) as follows:

queue.h                         queue.c
-------                         -------
				#include "queue.h"

typedef char queueElementT	typedef struct queueNodeTag {
				  queueElementT element;
				  struct queueNodeTag *next;
				} queueNodeT;

typedef struct queueCDT		typedef struct queueCDT {
        *queueADT;		  queueNodeT *front, *rear;
				} queueCDT;

Filling in queue functions:
The operations needed for our queue are mainly determined by the operations provided by an abstract queue, namely:
```
Enter
Delete
IsEmpty
```
However, as we've seen, we also need additional operations for setup and cleanup since we are implementing the queue in a programming language.
Here are the functions we need to implement...
For general queue operations:
- QueueEnter()
- QueueDelete()
- QueueIsEmpty()
Because we are programming in C (setup/cleanup):
- QueueCreate()
- QueueDestroy()
Because our implementation is with a linked list, we don't need:
- QueueIsFull()
Note: We use the convention of placing the data structure name at the beginning of the function name (e.g., QueueEnter). That will help us down the line. For example, suppose we use 2 different data structures in a program, both with IsEmpty operations--our naming convention will prevent the 2 different IsEmpty functions from conflicting.
Using our queue:

Now that we've decided on the data types and functions for a queue, we can see how our queue will be used:
```
#include "queue.h"

...

queueADT q1, q2;
char ch;

q1 = QueueCreate();
q2 = QueueCreate();

QueueEnter(q1, 'a');
QueueEnter(q2, 'b');
ch = QueueDelete(q1);

QueueDestroy(q1);
QueueDestroy(q2);
```
Note that we don't have to take the address of q1 or q2 when we pass them to queue functions. Using our new method of organizing types, a queueADT (like q1 or q2) is already a pointer to the thing that needs to be changed in queue functions.
Also note that the users of a queue cannot do something like:
```
q1->front = NULL;  /* WRONG! Won't work. */
```
(i.e., it won't compile) because they only get access to what is in the interface.

Note: The interface just tells the compiler that a queueADT is a pointer to some struct, but doesn't say what fields are present in the struct. So, users cannot access the fields of the struct.

This is great because it means they cannot mess up those fields. Since we are careful to write correct queue functions, we don't want users messing up our queue. Also, it allows us to change our implementation of the queue (to an array, e.g.) without affecting any of the code written by users of the queue.
QueueCreate() function:
Let's start by writing the function QueueCreate(), which creates a queue.
Note that our use of the queueADT (a pointer) with queue functions differs from how we might use it if it was a struct. Notably,
- For a new queue, we do not just pass a queue we declare to some initialization function, but rather, require a function to create a queue, initialize it, and return it.
- We pass the queueADT right to queue functions, not its address.
(Remember that from the queue user's end, a queue is a pointer, not a structure.)
Now, let's think about the QueueCreate() function.
1. Since a queueADT only gives us a pointer, how will QueueCreate() create the queueCDT?
2. Once we have a queueCDT, what do we need to do to its fields: front and rear?
3. How does the reference to the new queueCDT get out of the function QueueCreate() so that it can be used?
Our solution becomes:
```
queueADT QueueCreate(void)
{
  queueADT queue;

  queue = (queueADT)malloc(sizeof(queueCDT));

  if (queue == NULL) {
    fprintf(stderr, "Insufficient memory for new queue.\n");
    exit(1);  /* Exit program, returning error code. */
  }

  queue->front = queue->rear = NULL;

  return queue;
}
```
Here are the functions we have left:
```
return-type QueueDestroy(parameters);
return-type QueueEnter(parameters);
return-type QueueDelete(parameters);
return-type QueueIsEmpty(parameters);
```
Again, we want to be consistent in how we use a queue with queue functions. QueueCreate() is an exception since it must return a queueADT....
```
queueADT QueueCreate(void);
```
Nonetheless, since most functions will require some way to refer to the queue that they are to operate on, what should these functions take?
Answer: They should take queueADTs.
QueueDestroy() function:
QueueDestroy() is a function that must deallocate any memory used by the queue. Since a queue is kept track of with a queueCDT, this means any memory used directly or indirectly by the CDT.
Recall that a queueCDT is the following:
```
typedef struct queueCDT {
  queueNodeT *front, *rear;
} queueCDT;
```
What about the parts of the CDT?
- the front and rear point to nodes, so all the nodes they refer to should be gotten rid of.
- the whole structure itself doesn't exist before a call to QueueCreate(), and since it gets dynamically-allocated, it must be freed.
In conclusion, what QueueDestroy() should do is:
- free any nodes left in the queue.
- reset the pointers to the front and rear (for good measure).
- free the CDT.
Here is an implementation of QueueDestroy():
```
void QueueDestroy(queueADT queue)
{
  /*
   * First remove each element from the queue (each
   * element is in a dynamically-allocated node.)
   */
  while (!QueueIsEmpty(queue))
    QueueDelete(queue);

  /*
   * Reset the front and rear just in case someone
   * tries to use them after the CDT is freed.
   */
  queue->front = queue->rear = NULL;

  /*
   * Now free the structure that holds information
   * about the queue.
   */
  free(queue);
}
```

QueueEnter() function:

Now, let's think about what QueueEnter() must do. In general, it must add an element to the rear of the queue.

To enter something in the queue, we must do the following:

Create a new node:
```
---------
|   |   |
---------
```
Put data in it:
```
---------
| d | 0 |
---------
```

Link it into the list (i.e., the old rear node links to this new rear node):

front  rear------------------+
  |                          |
  v                          v
---------     ---------     ---------     ---------
| a | --+---> | b | --+---> | c | --+---> | d | 0 |
---------     ---------     ---------     ---------

Finally, change the rear link to the new rear:

front  rear---------------------------------+
  |                                         |
  v                                         v
---------     ---------     ---------     ---------
| a | --+---> | b | --+---> | c | --+---> | d | 0 |
---------     ---------     ---------     ---------

We should now ask ourselves whether this general algorithm will work in all cases. Are there any cases we have not examined?

Answer: Yes, starting out with an empty linked list.

Entering something into an empty list is a special case, because we'll have to change the front of the list too.

Here is our implementation of the function:

void QueueEnter(queueADT queue, queueElementT element)
{
  queueNodeT *newNodeP;

  /* Allocate space for a node in the linked list. */

  newNodeP = (queueNodeT *)malloc(sizeof(queueNodeT));

  if (newNodeP == NULL) {
    fprintf(stderr, "Insufficient memory for new queue element.\n");
    exit(1);  /* Exit program, returning error code. */
  }

  /* Place information in the node */

  newNodeP->element = element;
  newNodeP->next = NULL;

  /*
   * Link the element into the right place in
   * the linked list.
   */

  if (queue->front == NULL) {  /* Queue is empty */
    queue->front = queue->rear = newNodeP;
  } else {
    queue->rear->next = newNodeP;
    queue->rear = newNodeP;
  }
}

Helper functions:

Finally, suppose we abstract the operation of creating a new node and initializing it into its own function. Thus, we might rewrite the above as:

void QueueEnter(queueADT queue, queueElementT element)
{
  queueNodeT *newNodeP;

  /* Get a new node with the information stored in it. */

  newNodeP = NewNode(element);

  /*
   * Link the element into the right place in
   * the linked list.
   */

  if (queue->front == NULL) {  /* Queue is empty */
    queue->front = queue->rear = newNodeP;
  } else {
    queue->rear->next = newNodeP;
    queue->rear = newNodeP;
  }
}

Now, here is an implementation of a function that does just that:

static queueNodeT *NewNode(queueElementT element)
{
  queueNodeT *newNodeP;

  /* Allocate space for a node in the linked list. */

  newNodeP = (queueNodeT *)malloc(sizeof(queueNodeT));

  if (newNodeP == NULL) {
    fprintf(stderr, "Insufficient memory for new node.\n");
    exit(1);  /* Exit program, returning error code. */
  }

  /* Place information in the node */

  newNodeP->element = element;
  newNodeP->next = NULL;

  return newNodeP;
}

Of course, this function definition will go in queue.c since it is part of the implementation. However, this function is different than the others because it is only a helper function for completing the queue, and is not meant to be called by people using a queue.

Thus, you'll note a few differences:

The function is declared to be a static function. This means that it can only be called from other functions within the same source code file, i.e., queue.c.
The name of the function is not prefixed with Queue. Again, because this function's scope is confined to queue.c it is not likely to conflict with another function named NewNode().

Finally, since this function should have a prototype, where should we put its prototype?

Since NewNode has been restricted to queue.c, it prototype must go there. In other words, since NewNode is not meant to be publicly accessible to people using the queue, its CANNOT be prototyped in queue.h.

So, the format of queue.c will look something like:

...

#include "queue.h"  /* for interface types, prototypes, etc. */

/* Implementation type definitions. */

...

/************* Helper function prototypes ************/

/*
 * Function: NewNode
 * Usage: p = NewNode(element)
 * -----------------------------------
 * Returns a pointer to new node with the
 * specified element filled in.
 */
static queueNodeT *NewNode(queueElementT element);

/**************** Function definitions ***************/

...

Comments:
Note how we have used a static helper function (the function NewNode()) to help hide the details of a data structure.
It is left up to the reader to write the other queue functions: QueueDelete() and QueueIsEmpty().