Lab: 30 - Double-Ended Queue Implementation

Assigned

Wednesday, 8 November 2023

In this lab, you will practice implementing (and testing!) your own specific collection. Namely, a double-ended queue (aka Dequeue).

Your double-ended queue will implement the basic functionality of the Java library Deque but with slightly different method names.

Preparation

• Create a new Java project in Eclipse.
• Import the file Dequeue.java into your new Eclipse project. The file is at /home/jimenezp/csc207/Lab-DequeueImp/Dequeue.java
• Read the provided code. It will give you information about starting values for your double-ended queue implementation.

Background

A double-ended queue allows access at “both ends.” In other words, it acts like both a queue (add to end, retrieve from front), and a stack (add to front, retrieve from front). Plus, it allows you to retrieve from the end as well. Thus, it is like a mini-Swiss army knife of data structures. (A list would probably be the full-on Swiss army knife, since it allows arbitrary access.)

Our dequeue is built on a circular array that supports wrapping around if an index would go beyond the end of the array. It also will expand its capacity when needed.

Our dequeue implementation will support six core operations:

• two that “peek” at the collection without modifying it,
• two that modify it by removing from either end, and
• two that modify it by adding to either end.

void addFront( AnyType x ) // Insert x at front 
void addRear( AnyType x )  // Insert x at rear 
AnyType getFront()         // Return item at front (peek)
AnyType getRear()          // Return item at rear (peek)
AnyType removeFront()      // Return and remove item at front
AnyType removeRear( )      // Return and remove item at rear

Exercise 1 - Prediction

Assume that you have a double-ended queue named dq that holds Integers. What do you expect the output to be from the following set of commands?

dq.addFront(3);
dq.addRear(5);
dq.addFront(7);
dq.addFront(6);
System.out.println(dq.removeRear()); 
System.out.println(dq.removeRear()); 
System.out.println(dq.removeFront()); 
System.out.println(dq.removeRear());

Check your prediction with the staff or check your prediction with your program once you complete the Dequeue class.

Exercise 2 - Complete the Dequeue Class

Review the methods and data fields in the Dequeue.java class. Note that they may be different locations than you are used to finding them in. Make sure you read to the bottom of the file to find the helpful, provided methods.

You will need to complete these methods:

• decrement
• isEmpty
• makeEmpty
• getFront
• getRear
• removeFront
• removeRear
• addFront
• addRear

Note that the default size of the internal array is deliberately small so that you can easily test the automatic expansion of the queue.

If you want to confirm your code before moving onto the next exercise, you can create a program with a main method, create a dequeue and invoke your methods a few times to see how well it works and to make corrections.

Exercise 3 - JUnit Tests

In your Eclipse project, create a New JUnit Test Case. You will create at least 12 test methods to confirm that your program is working.

At a minimum you must create tests for:

• Adding an item at the front
• Adding an item at the rear
• Adding and removing at the front and rear in several different combinations of adds and removes and testing that the correct element is found at the front or the rear
• Adding enough elements that the array must wrap and that elements are removed in the correct order
• Adding enough elements that the array must expand
• Testing the isEmpty method in several circumstances
  • Empty before anything is added
  • That it is NOT empty after adding an item to the front of a previously empty dequeue
  • That is is empty after removing that item
  • That it is NOT empty after adding an item to the rear of a previously empty dequeue
  • That is is empty after removing that item
  • That it is NOT empty after adding an item to the front and rear of a previously empty dequeue
  • That it is empty after removing the items from the previous test
• Test that an exception is thrown when trying to remove an element from an empty list and that a customized exception message message is correct.
• Test that the makeEmpty method clears the dequeue

To test throwing an exception in JUnit use this format in your test method:

Throwable exception = assertThrows(NoSuchElementException.class,() -> {
	// code being tested
       dq.getFront();   // this is an example, where dq is a Dequeue
    });
    assertEquals("Empty", exception.getMessage(), "Empty: get front exception");

Lab Submission

Submit:

1. (2 points) Your Dequeue.java class
2. (2 points) Your JUnit test case class, screenshot of the JUnit panel showing that all tests pass. You must have at least 12 tests.

Remember: Do not use magic numbers, write your code anticipating errors and print user-friendly error messages, all your public methods should be well documented (use Javadoc comments). Please include comments or organize your code and report in a way that will help the grader to find the answer to the exercises or posted questions.