Looking for Help with Assignments?
-Instructors and Lead Instructional Assistants have a combined 10+ hours of Office Hours, open to all sections. See times/locations here.
-Piazza (found in the Canvas sidebar) provides fast support from Course Staff and other Students. Be sure to search to see if someone has asked a similar question!
-If you need a computer to complete work on, iLab machines can be found in the CSL (Hill 252) and surrounding rooms.
Theme Park Queue - 10 Course Points
The purpose of this assignment is to learn how to implement the methods of a Queue using a linked list.
You can download and submit the project files via Autolab.
Refer to our Programming Assignments FAQ for instructions on how to install VSCode, how to use the command line and how to submit your assignments.
See this video on how to import the project into VSCode and how to submit into Autolab.
The assignment has one component:
Coding (10 points) submitted through Autolab.
Overview
The ThemeParkQueue.java class represents a Linked-List implementation of a simple queue. The class attributes and constructor are provided.
You must fill in the code for the enqueue(), dequeue(), and interleaveQueue() methods, to finish the Queue of Strings and enable the Theme Park Queue Driver visualization.
The ThemeParkQueue class is a queue, implemented using a Linked-List. It holds two pointers, one to the front of the line and one to the end of the line. This allows you to enqueue riders at the end of the line, and dequeue them from the front of the line.
Each node in the linked-list is a Rider, which is represented by an LLNode<String> where the String data is the name of the rider. The next field of each LLNode should point to the node directly behind them in line.
EX:
Working with LLNode<> objects
For assignments/labs in CS112, we will use a cs112.jar file containing useful classes. This includes the LLNode<> class, which implements a linked list node. There are other classes in this jar file, which you will be introduced to in later labs/assignments.
- The LLNode class takes in a generic type, which means it can store any type of data. In this lab you will be working with nodes that have String data – to have nodes with String data we can use LLNode<String>
- Making a node: LLNode<T> newNode = new LLNode<>(data) — replace T with a type
- Note that the data must be passed in for the constructor, and the data of a node can not be changed later (aka it is immutable)
- Methods:
- getNext() – returns the next node in the linked list
- getData() – returns the data stored in the current node
- setNext(LLNode<T> nextNode) – sets the next node of the current node to nextNode
Directions
- DO NOT add new import statements.
- DO NOT add any new class attributes
- DO NOT change any of the method’s signatures.
- DO NOT modify the given constructor.
To complete this Lab, you must implement the enqueue, dequeue, and interleaveQueue methods. The method signatures are already given, do not modify these or add any new ones.
enqueue(String toAdd)
This method adds a new String to the Linked List, by creating a new Rider node to hold the given String. You should always enqueue to the END of the line.
Remember, each node has a next attribute, which is a reference to the LLNode directly BEHIND them. So if Rider1 is in front of Rider2 in line, then Rider1 -> Rider2. So, endOfLine.getNext() should always be null, since there is no one behind them.
If the line is empty:
- Create a new LLNode, and set its data to the given name toAdd.
- Set frontOfLine and endOfLine both equal to that new rider (since if the line is only 1 person long, they are both at the start and the end).
- Increment the lineLength attribute by 1.
Else if the line is not empty:
- Create a new LLNode, and set its data to the given name toAdd.
- Insert that node AFTER the current endOfLine
- Update the endOfLine reference
- Increment the lineLength attribute by one.
dequeue()
This method removes the Rider at the front of the line, and returns their name.
If the line is empty, then return null.
If the line is not empty, then remove the node at the front of the Queue and return the name of the rider which was removed. Remember to decrement the lineLength attribute by one. Remember to update the references properly.
interleaveQueue(ThemeParkQueue otherQueue)
In this method you will be working with two ThemeParkQueue objects. We want to combine the riders from this queue and the riders from “otherQueue” into one line by alternating between the two. The rider at the front of this queue goes first, then the rider at the front of otherQueue, then the next rider from this queue, and so on. If one queue runs out of riders before the other, the riders still waiting in the longer queue follow at the end, in the same order they were in.
Do not relink nodes yourself. Build this method using the enqueue() and dequeue() methods you already wrote. You may create as many new ThemeParkQueue objects as you need. Remember that enqueue() and dequeue() already update frontOfLine, endOfLine and lineLength, so you don’t need to change those attributes directly.
Once we have interleaved the riders from otherQueue into this ThemeParkQueue, otherQueue should be empty, with a lineLength of 0, since no more riders are left in that queue.
Driver
Once you implement your code, you can run the Driver.java file and interact with the driver. There are 2 panels, each is its own queue. You can enqueue and dequeue from Q1 or Q2 independently. Once you have implemented interleaveQueue(), you can use the 2 buttons on the bottom to interleave Q1 to Q2, or interleave Q2 to Q1. It is best to test edge cases in both directions so you can use these to help. Pay attention to the lineLength’s of the queues.
You can use this Driver to test your code, but it is still useful to write JUnit test cases, in case the driver does not catch all cases.
Writing JUnit Tests
You do not have to submit this, this is for you to test your own code.
Since this queue implementation contains public methods, and represents a generalized queue of strings, we can test it independently of the driver using a test class.
In the main project folder, there exists a “test” folder next to the “src” folder. This contains a JUnit test class, which can run and test pieces of your code. To compile and run these tests, you must install the Test Runner extension. See the Programming FAQ for more info on VScode extensions.
The three tests are for enqueue(), dequeue() and interleaveQueue(), you fill these tests in. Once you do, remove the fail() statements at the bottom and run.
You are provided with a premade JUnit test class for ThemeParkQueue. You can finish writing the test methods, by using JUnit test methods (assertTrue(), assertFalse(), assertEquals()) in order to test your code.
Try testing enqueue using the lineLength attribute. Then, test to see if the queue dequeues the strings in the correct order (FIFO).
Tests not running?
First, make sure you’re in the right folder and the tests are implemented. Next, if you have the “Code Runner for Java” or Oracle “Java” extension, make sure you uninstall those extensions. Remember that you must fill in the tests for enqueue() and dequeue().
VSCode Extensions
You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:
Importing VSCode Project
- Download ThemeParkQueue.zip from Autolab Attachments
- Unzip the file by double-clicking.
- Open VSCode
- Import the folder to a workspace through File > Open Folder
Executing and Debugging
- You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.
- If you choose the Terminal:
- first navigate to ThemeParkQueue directory/folder
- to compile: javac -d bin src/queue/*.java
- to execute: java -cp bin queue.Driver
- NOTE: if you have ThemeParkQueue (2) -> ThemeParkQueue or CS112 -> ThemeParkQueue in VS Code, open the INNERMOST ThemeParkQueue through File -> Open Folder.
- first navigate to ThemeParkQueue directory/folder
Before submission
COMMENT all printing statements you have written from ThemeParkQueue.java
Collaboration policy. Read our collaboration policy on the course syllabus.
Submitting the assignment. Submit ThemeParkQueue.java separately via the web submission system called Autolab. To do this, go to Autolab and find the correct assignment and submit your Java file.
Getting help
If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.
- Find instructors and Instructional Assistants office hours here
- In addition there is the Coding and Social Lounge (CSL) , a community space staffed with student community managers which are undergraduate students further along the CS major to answer questions.
By Colin Sullivan
