In this lab, you will create an abstract data type, using a doubly-linked circular structure to store the values and links. You must create it by your own and not use any existing containers.
You will need a QueueNode. You can use a struct for this, as each node will not have any associated functions. It will have members for data, and the next and previous pointers. Data will be positive integers. There will be no NULL pointers. Every NEXT pointer will point to a QueueNode as will every PREV pointer.
You will create a new node when the queue is full. As you take the data out, you will NOT remove the node. Use a sentinel value of -1 to indicate a node is empty.
You will create a Queue class. It will have the data and function members described below. The queue is a first in first out structure. You add to the back and can only look at or take off the front. You will use a circularly linked structure to implement this queue. In your class you will only have the QueueNode pointers to the front and to the back:
QueueNode *front // first item in the queue, where you take the item off
QueueNode *back // last item in the queue, where you add a new item to
You will implement these functions with appropriate parameters and return types in your Queue class:
addBack() // puts on item at the end of the queue or
// creates a new node to store the item if the queue is full
getFront() // returns the value at the front of the queue
removeFront() // removes the first item in the structure
The removeFront() function only replaces the value in the front node by inserting the sentinel. It does nothing else. The getFront() and removeFront() functions will return a -1 if the queue is empty when the function is called. Include appropriate constructors and destructors. You will NOT have a data member (or variable) for size.
HINT: You should sit down and design the whole program before touching a keyboard. For the queue, sit down with a pencil and a piece of paper and study the required pointer manipulations. Figure out how you will test if the queue is full or empty by just using the front and back pointers. After you complete the design, you should develop your code first using pseudocode. Then convert it to C++.
You must also write a driver program that uses your queue to demonstrate it works correctly. You will prompt the user with a menu. The options should be:
a. Enter a value to be added to the queue,
b. Display first node (front) value,
c. Remove first node (front) value,
d. Display the queue contents,
x. Exit
For example, after you display the menu, the user enters a. Your program then reads the integer and put it in the back node. You can have the user type a 7, or you have a