Doubly Linked Lists and Queues

The goal of this lab period is to build a Doubly Linked List that acts as Queue.

---

Tasks

Testing

As always, as you are coding up this project create testing files for each class you create exercising the public methods implemented in this class.

CellQueue

Last week, we built a CellStack class that helped us keep track of a stack of Sudoku Cells. Conveniently, this project will also focus around 'Cell's, but with a different purpose. Additionally, we'll also want to organize them in a Queue rather than a stack, so this week we'll be building a CellQueue. It will look and work quite similarly to the CellStack from last week, except that adding Cells to the queue will add them to the opposite end that we take them out from.

1. Setup

   Make a new folder for this week's project.

   Create a new java file called CellQueue.java

2. Define the CellQueue class

   Define a public class CellQueue. We will create it with a standard LinkedList structure in mind. The main difference between this class and the LinkedList class from project 3 will be that each Node keeps track of not only the Node following it, but also the Node preceeding it.

3. Create a container class (a Node)

   As in the LinkedList class, we will use Nodes. This time, however, each Node will have 3 fields: a field of type Node called next, a cell field of type Cell (you will build this class in the project itself), and another Node field called prev. As you've had practice with Nodes in a few projects now, we'll let you decide how you want to build your Node class (under the constraint that every Node should have both a next and prev pointer).

4. Create fields and methods for the CellQueue class

   Similar to the LinkedList from project 3, we'll want fields to store the Node head and the int size. In addition, we'll now want to also store the Node tail, the end of the list. We'll also implement the following methods:

   • public CellQueue() constructor that initializes the fields so it is an empty queue.
   • public void offer(Cell cell) inserts the cell at the end of the queue.
   • public Cell peek() returns but does not remove the Cell at the front of the queue.
   • public Cell poll() returns and removes the Cell at the front of the queue.
   • public int size() returns the number of Cells in the queue.

Cell Class

In a shocking twist, this project will be based around a 2-D Landscape consisting of individual Cells. Each Cell will have an underyling type; specifically, each Cell will either be an

• unobstrocted cell (free cell),
• obstructed cell,
• start cell,
• or target cell.

1. Declaring the enum Type

   To implement this, first create your Cell class then add the following enum declaration:

   public class Cell {
       public enum Type {
           FREE, OBSTACLE, START, TARGET
       }        
   }

   An enum is something like a restricted class in Java, in that you're declaring a type of object that can only take on specific values. In this case, we're declaring that the enum type can either be free, obstructed, start, or target.

2. Cell's Fields

   Each Cell should have the following fields:

   • boolean visited for determining whether we've visited this Cell yet
   • Cell prev for determining which Cell we came from to visit this Cell
   • int row, col for determining which row and column this Cell belongs to in the Landscape
   • Type type for determining which type of Cell this is

3. Cell's Methods

   All of Cell's methods are basically just getter/setters, but they'll become more obviously useful in the Landscape class.

   • public Cell (int row, int col, Type type) constructor that sets up the row, col, and type as specified; prev should be null and visited should be false.
   • public int getRow() returns the row
   • public int getCol() returns the column
   • public Type getType() returns the type
   • public boolean visited() returns visited
   • public Cell getPrev() returns prev
   • public void visitFrom(Cell c) sets visited to true and prev to c
   • public void reset() sets visited to false and prev to null

---

When you are done, you can proceed to the project.

---