CSC 207 CSC 207.01 & .02- Algorithms and Object-Oriented Design Spring 2022 Home Schedule Class Slides Labs Assignments Resources Lab: Linked List Queue Implementation In the last few labs, you have worked at implementing some canonical data structures using an array as the underlying storage structure. In this lab, you will switch to implementing a singly-linked queue using a linked-list to store data. Creating linked lists and queues in Java are rather similar to the same operations and data structure that you might have enountered in CSC161 and C. You will work with the following files: QueueNode.java stores queue items. Queue207.java defines an interface for queue operations. Queue207Implementation.java implements the Queue207 interface. Preparation Create an Eclipse project called queues. Copy the QueueNode.java and Queue207.java source files from the following path in MathLAN and import them to the Eclipse project: /home/johnsonba/csc207/code/ QueueNode A Queue can be implemented by a singly linked list of QueueNodes. The QueueNode.java class has the following structure: public class QueueNode
{ private AnyType data; // data is stored inside a node. private QueueNode next; // this field references the next node. public QueueNode ( ) { data = null; next = null; } public QueueNode( AnyType origData, QueueNode origNext ) { data = origData; next = origNext; } } The data field stores a reference to some actual data. The next field stores a reference to the next QueueNode of the list. This class has two overloaded constructors: one that sets the data and next fields to null and the other sets them to parameters passed to the constructor. You will need to write the getter and setter methods for data and next fields for QueueNode. By considering the above structure, the Queue207Implementation class contains three private fields: numberItems, head, and tail. numberItems specifies the number of items in the queue. head and tail references mark the two ends of the queue as shown in the following figure: Items are deleted from the head reference and inserted at the tail reference. This indicates that the items are placed into the queue in the order that they are inserted there. In other words, the item, referenced by head, is the first item inserted in the queue while the item, referenced by tail, is the last item inserted in the queue. Note that we keep track of both ends of the linked list to avoid traversing the list every time we need to add an item to the queue. The implementation details of important methods in Queue207Implementation class are explained below: Queue207Implementation constructor: initializes three fields: numberItems, head, and tail. numberItems is initialized to zero. head and tail are initialized to null. add method: instantiates a new QueueNode that contains the specified data and null in the next field. The next field of the QueueNode, referenced by the old tail of the queue, is updated to reference the new QueueNode. The tail field of the queue is updated to reference the new QueueNode. If the new QueueNode is the first QueueNode of the queue, the head and tail fields are updated to reference the new QueueNode. remove method: extracts data from a QueueNode referenced by the head field and removes the node The head field is updated to reference the next QueueNode of the queue. If data is extracted from the last QueueNode of the queue, the tail field is updated to reference null. Remember that Java will automatically manage "garbage collection" for you - so there is no free method. Tasks 1. Write the Queue207Implementation class that implements the Queue207 interface. Provide implementations for the constructor, add, remove, element, and size methods. 2.Write Queue207ImplementationTester class that calls all of the methods. You must: create a queue and call the following methods in order: add, add, remove, element, size, add, size, remove, remove, size. (6 points) For your lab write up, include a copy of your Queue207Implementation.java and Queue207ImplementationTester.java source files and your output for step 2 (copy and paste the console output, a screenshot of the result, or print to a file). Acknowledgement This lab is based on a material made by Henry Walker. This derivative work is used and licensed under a Creative Commons Attribution-NonCommercialShareAlike 4.0 International license. This course is adapted from prior courses taught by Shervin Hajiamini, John Stone, Sam Rebelsky, Anya Vostinar, and Jerod Weinman and used by permission. Other authors' contributions are noted when used or adapted.
