Skip to Main Content

Data Structures

Computer Science Department

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 data structure.

Start your assignment early! You need time to understand the assignment and to answer the many questions that will arise as you read the description and the code provided.

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 an Linked-List implementation of a simple queue. The class attributes and constructor are provided, along with the pop() method.

You must fill in the code for the enqueue() and dequeue() 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 a simple node containing only two attributes, name and next. The next field of each Rider node should point to the Rider node directly behind them in line.

EX:

“Rider One” -> “Rider Two” -> “Rider Three” -> “Rider Four”

^frontOfLine                                                                   ^endOfLine

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 and dequeue methods for the linked-list based queue. 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 Rider node has a next attribute, which is a reference to the Rider directly BEHIND them. So if Rider1 is in front of Rider2 in line, then Rider1 -> Rider2. So, endOfLine.next should always be null, since there is no one behind them.

If the line is empty (frontOfLine/endOfLine are null):

  1. Create a new Rider node, and set its .name attribute to the given name toAdd.
  2. 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).
  3. Increment the lineLength attribute by 1.

Else if the line is not empty:

  1. Create a new Rider node, and set its .name attribute to the given name toAdd.
  2. Insert that node AFTER the current endOfLine (using endOfLine.next)
  3. Set endOfLine to that new node you just enqueued, to mark it as the new end of the line.
  4. 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 (frontOfLine/endOfLine are null), then return null.

If the line is not empty:

  1. Save the name of the Rider at frontOfLine in a temporary String variable.
  2. Set frontOfLine equal to the second Rider in line.
  3. Decrement the lineLength attribute
  4. Return the name you stored in the temp String variable.

a

Driver

Once you implement your code, you can run the Driver.java file and interact with the driver. It will show an empty box, with two buttons “Enqueue Rider” and “Dequeue Rider”, as well as a label displaying “Line Length: 0”.

If you click the Enqueue Rider button, a Rider will be enqueued onto the line (the front of the line is the left side of the Driver window). You can enqueue as many Riders as you’d like. When you click the Dequeue Rider button, the Rider all the way to the left will be dequeued.

Note: the driver will not check that you are properly returning the String name when dequeueing.

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 two tests are for enqueue() and dequeue(), and you must 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

  1. Download ThemeParkQueue.zip from Autolab Attachments.
  2. Unzip the file by double-clicking.
  3. 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.
  • How to debug your code
  • If you choose the Terminal:
    • first navigate to ThemeParkQueuedirectory/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.
To run JUnit tests: right click test/QueueTest.java in VS Code and select Run Tests. 

Before submission

COMMENT all printing statements you have written from ThemeParkQueue.java 

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit ThemeParkQueue.java separately via the web submission system called Autolab. To do this, click the Labs and Assignments link from the course website; click the Submit link for that assignment.

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

  • Find instructors office hours here
  • Find tutors office hours on Canvas -> Tutoring
  • Find head TAs office hours here
  • In addition to office hours we have the Coding and Social Lounge (CSL) , a community space staffed with ilab assistants which are undergraduate students further along the CS major to answer questions.

By Colin Sullivan