Queue - Linked-List Implementation - Types

Here, besides discussing the queue data structure, we will demonstrate how to better hide the details of a data structure using ADTs/CDTs and generic type definitions.

Abstract idea of a queue:
The queue is another data structure. A physical analogy for a queue is a line at a bank. When you go to the bank, customers go to the rear (end) of the line and customers come off of the line (i.e., are serviced) from the front of the line.

Aside: In fact, other English-speaking countries use this term for a line, e.g., they might say "Queue up!" rather than "Get in a line!"

Like a stack, a queue usually holds things of the same type. We usually draw queues horizontally. Here's a queue of characters with 3 elements:
```
queue
-------------
| a | b | c |
-------------
  ^       ^
  |       |
front    rear
```
The main property of a queue is that objects go on the rear and come off of the front of the queue.
Here are the minimal set of operations we'd need for an abstract queue:
- Enter (or Insert)
  Places an object at the rear of the queue.
- Delete (or Remove)
  Removes an object from the front of the queue and produces that object.
- IsEmpty
  Reports whether the queue is empty or not.
Order produced by a queue:

Queues are useful because they produce a certain order in which the contents of the queue are used. Let's see what order that is by looking at a queue of characters. Now, what would a particular sequence of Enter and Deletes do to this queue:
```
queue
-------------
| a | b | c |
-------------
  ^       ^
  |       |
front    rear
```
Now, Enter(queue, 'd')...
```
queue
-----------------
| a | b | c | d |
-----------------
  ^           ^
  |           |
front        rear
```
Now, ch = Delete(queue)...
```
queue           ch
-------------   -----
| b | c | d |   | a |
-------------   -----
  ^       ^
  |       |
front    rear
```
You'll notice that the queue enforces a certain order to the use of its contents. Is the ordering of the queue Last thing In is the First thing Out (LIFO) or First Thing In is the First thing Out (FIFO)?
Answer: Queues produce FIFO order. Remember that stacks produce LIFO order.

Implementing a queue:

Since a queue usually holds a bunch of items with the same type, we could implement a queue with an array. However, here we'll use a linked list implementation.

Remember that a linked list can:

hold as many objects as memory can hold (i.e., it's not a fixed size).
grow easily without having to copy over the old contents.

Note: Copying over is the problem incurred with a dynamic array that has to be made bigger.

Recall that linked lists are made up of things called nodes:

A Node ----------------- | | | | Data | Link -+--> | | | -----------------
A node contains 2 main parts:

some data and,
a link to the node after it (for a singly-linked list).

In C, we know that these links will be pointers. Here is an example singly-linked list that holds characters.

list
  |
  v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------

First, we must decide how the contents of this linked list corresponds to the structure of the queue.

A logical choice would be to make the beginning of the linked list the front of the queue and the end of the linked list the rear of the queue.

Given this representation, we'll rename the link to the beginning of the list to front:

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

Will this representation be sufficient for adding and removing things from the queue?

Answer: Yes, however, we see one inefficiency in that, unlike the stack, things aren't added and removed from the same end. To add something to a queue, that thing must go on the rear. Currently, the only way to get to the end is to traverse to the end of the list. We can be more efficient if we keep track of the rear of the queue with a direct link.

Our augmented representation looks as follows:

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

Empty Queue

Last, we'll need a representation of an empty queue. We'll make at least the front, but also maybe rear, link to nothing when the queue is empty. In C, this means they will contain NULL pointers.

C code:
Now, let's think about how to actually code this queue of characters in C...
We'll put this data structure in its own module, thus, we'll want to create files queue.h and queue.c.
There are 2 main parts to a C data structure: the data types needed to keep track of a queue and the functions needed to implement queue operations.
Organization of data types for a queue:
Our goal is to have a type for a queue, so that people using our queue can define queue variables, and pass them to queue functions. For example, they'll do something like the following:
```
#include "queue.h"

...

type-of-a-queue q1, q2;
char ch;

/* Setup queues. */

QueueEnter(ref-to-q1, 'a');
QueueEnter(ref-to-q2, 'b');

ch = QueueDelete(ref-to-q1);

/* Cleanup queues. */
```
Notice how each queue operation needs some way to refer to a specific queue (so that we can have more than one queue at a time).
However, we'll also want to abstract the type of an element. In other words, we want to make it very easy to change the type of an element by isolating it in one place, in a type definition.
Let's consider the organization of types between our queue module files:
```
queue.h				queue.c
-------				-------
				#include "queue.h"

type-of-an-element

type-of-a-queue
```
The interface (.h) for the queue will need to have a type for the queue (for people to define queue variables) and the type of an element (for functional prototypes)...
However, while people using the queue will need to know the type-of-a-queue, and thus, it will need to be in the header file, we want to hide any of the internals of the type-of-a-queue in the .c file. Thus, the type-of-a-queue should be broken up into an abstract and concrete part.
- The concrete part is a structure with all the pieces of data needed for a queue, and which is hidden in the implementation. (Remember that we isolate this type from users of the queue, i.e., they do not need to know that the queue is implemented as a linked list. Furthermore, isolating the type will prevent them from being able to mess up the queue.)
- The abstract part is a pointer to such a structure, which is publicly available to users of a queue.
Therefore, our goal is to have the following:
```
queue.h				queue.c
-------				-------
				#include "queue.h"

type-of-an-element

abstract-type-of-a-queue	concrete-type-of-a-queue
```
Finally, we need one additional type, one for a node, since we are using a linked list implementation. This type only has to do with how the queue is implemented, not in how it is used, so it goes in the implementation file, giving:
```
queue.h                         queue.c
-------                         -------
                                #include "queue.h"

type-of-an-element		type-of-a-node

abstract-type-of-a-queue        concrete-type-of-a-queue
```
We'll get the types from queue.h in queue.c since we always include the header for a module in the implementation (.c) part of the module.
ADTs and CDTs:

Let's start filling in the types for a queue. First, we want to write a queue that is very generic. The fact that this queue holds a character is only particular to this exercise. It should be easy to change the type of things held in the queue.
Let's introduce a type name for the type of things held in the queue.
```
typedef char queueElementT;
```
This will go in the header file, since we need it for the queue function prototypes.
Next, elements of the queue are being stored in a linked list. Recall that linked lists are made up of nodes that contain both an element and a pointer to the next node.
Thus, we can define a node by combining these 2 parts into one type with a struct (and place it in the implementation file):
```
typedef struct queueNodeTag {
  queueElementT element;
  struct queueNodeTag *next;
} queueNodeT;
```
Next, we need something that holds all the information needed to keep track of the queue. We already decided that we will use a pointer to the node at the front and the node at the rear.
Since these pointers have to do with the implementation of the queue, we put them in the concrete-type-of-a-queue, struct queueCDT (which also goes in the implementation file):
```
typedef struct queueCDT {
  queueNodeT *front, *rear;
} queueCDT;
```
Finally, in the header file, we must fill in what the abstract-type-of-a-queue is as follows:
```
typedef struct queueCDT *queueADT;
```
NOTE: C will allow us to use a pointer to a type that has not been defined yet only if that type is a structure that we name with a tag, as in struct queueCDT above. That is why we must use a tag name with the CDT when we define it in queue.c. In other words, the struct mentioned in queue.h, struct queueCDT, must be named using the form "struct tag-name" and have the same tag name as the CDT defined in queue.c.

Finally, we have the following:
```
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;
```
In other words, things that need to be part of the interface go in queue.h and things that are hidden as part of the implementation go in queue.c.
Comments:
Note how we have used:
- ADTs/CDTs (the type queueADT placed in queue.h and queueCDT placed in queue.c), and
- generic type definitions (the type queueElementT)
to help hide the details of a data structure. That way, if we decide to change the implementation of the data structure (e.g., to an array implementation), we need not change the interface and how the data structure is used. Also, we have an easy way to change the type of things held in the queue.
You should be able to answer the following questions:
- Why do we use queueElementT and why must it be in the interface?
- Why must we name the CDT using a structure tag name, as in struct queueCDT?
- Does the interface or people who are just using a queue have any information about what are the fields in the structure that is the CDT? Do they need to know what these fields are? Why or why not?