$24
Lab #7 Circular Linked List Solution
Goals
Implement a circular linked list data type
Learn how to modify data in a linked list
In this lab, we will create a queue data structure utilizing circular linked list.
Requirements
For simplicity, out circular linked list will only contain integer as values.
Note: You are not allowed to use any standard containers for this lab.
QueueNode Data Structures
Create a struct that is called QueueNode that represents each node. It contains:
next, a pointer to the next Node object
prev, a pointer to the previous Node object
val, integer value the specific Node contains
Queue class
Queue class has the following member variables:
head, a pointer to the first QueueNode object in the queue
Note: Constructor and destructor are needed for the Queue class, and destructor should free all the memories of nodes in the queue.
Note: You cannot have a variable to keep track of the size of the queue. (or the number of nodes the queue holds)
Queue class also has the following member functions:
bool isEmpty() checks if the queue is empty. If so, returns true; otherwise, return false.
void addBack(int val) takes a user-inputted integer, creates a QueueNode with user-inputted integer, and appends it to the back of the list.
int getFront() returns the value of the node at the front of the queue.
void removeFront() removes the front QueueNode of the queue and free the memory.
void printQueue() traverses through the queue from head using next pointers, and prints the values of each QueueNode in the queue.
Note: Make sure the user-inputted integer is validated in menu, before it is passed into addBack(int).
Menu
The menu should provide the following options:
Add a value to the back of queue
Display the front value
Remove the front node
Display the queue’st conten
Exit
For option #1, the menu should prompt user for an integer input to be added to the queue. The input must be validated before being passed into the addBack(int) function.
For option #2, #3, #4, what happens when the queue is empty? What function can help you out in this situation?
Note: It is important to know that after each function operation, you need to reassign the prev, next pointers for the QueueNodes inside the queue, so that linked list structure is preserved.
HINT: It is very important to sit down, design the whole program and understand the steps of each operation before you start coding. Think about edge cases carefully (when the queue is empty, or only have 1, or 2 nodes).
Important:
For this lab, you cannot implement the linked list operations using functions from outside source. You need to write all the functions by yourself!
If you do not use a circular linked list structure for queue, your lab will not be graded.
Example run of the program
Welcome to my queue!
Choose from following options:
Enter a value to be added to the back of queue
Display first node (front) value
Remove first node (front) value
Display the queue contents
Exit
1
Please enter a positive integer:
15
Choose from following options:
Enter a value to be added to the back of queue
Display first node (front) value
Remove first node (front) value
Display the queue contents
Exit
1
Please enter a positive integer:
5
Choose from following options:
Enter a value to be added to the back of queue
Display first node (front) value
Remove first node (front) value
Display the queue contents
Exit
1
Please enter a positive integer:
10
Choose from following options:
Enter a value to be added to the back of queue
Display first node (front) value
Remove first node (front) value
Display the queue contents
Exit
3
Choose from following options:
Enter a value to be added to the back of queue
Display first node (front) value
Remove first node (front) value
Display the queue contents
Exit
2
The first node value is: 5
Choose from following options:
Enter a value to be added to the back of queue
Display first node (front) value
Remove first node (front) value
Display the queue contents
Exit
4
Your queue is: 5 10
