CIT 594 Assignment 1: Linked Lists
Spring 2013, David Matuszek

Purposes of this assignment

To give you experience implementing linked lists
To give you a better understanding of ADTs (Abstract Data Types)
To teach you how to write and use Iterators
To give you some experience coping with generics

General idea of the assignment

Write linked-list implementations of stacks, queues, and deques, with iterators for each, and display their operation in the provided GUI.

Definitions

Data type: A set of values and their associated operations. For example, the int data type consists of the values Integer.MIN_VALUE through Integer.MAX_VALUE, with the operations add, subtract, etc. In Java, every class definition is a definition of a data type.
Abstract Data Type (ADT): A set of values and their associated operations, where the implementation of those values and operations is hidden from the user; all access is via the methods that are provided.
Application Programmer Interface (API): A class (or related group of classes) and the operations that they provide to the user.
Link: A pointer or reference.
Node: A data structure that typically holds a value and one or more links. Nodes are the basic building blocks for many data structures.
Sequence: An ordered collection of values, typically having a first and a last value.
Linked list: A data structure that consists of a sequence of nodes linked together in a linear fashion.
Singly-linked list: A linked list in which each node links to the next node. Thus, from any given node it is possible to find the next node in the sequence, but not possible to find the previous node.
Doubly-linked list: A linked list in which each node has links to both the next node and the previous node in the sequence. Thus, from any given node it is possible to find both the next node and the previous node.
Stack (LIFO data structure): A sequential data structure in which all operations (add, remove, peek at) are performed at the same end. Sometimes called a Last In, First Out data structure.
Queue (FIFO data structure): A sequential data structure in which additions are performed at one end and deletions are performed at the opposite end. Sometimes called a First In, First Out data structure.
Deque (pronounced “deck”): A sequential data structure in which additions and deletions may be performed at either end. Despite being more general than either a stack or a queue, deques have many fewer uses.
Iterator: A data type that keeps track of the “current” value in a sequence, and can return the next value (or tell whether there is a next value). In Java, iterators are provided by the Iterable and Iterator interfaces.

Detailed specification

Implement the following classes as ADTs:

public class Stack<T> extends AbstractSequence<T>
public class Queue<T> extends AbstractSequence<T>
public class Deque<T> extends AbstractSequence<T>

with the following public operations (methods):

Operation	Stack	Queue	Deque	In the GUI
constructor	Just use the default constructor. A typical call would be: `Stack<String> myStack = new Stack<String>();`	Just use the default constructor. A typical call would be: `Queue<String> myQueue = new Queue<String>();`	Just use the default constructor. A typical call would be: `Deque<String> myDeque = new Deque<String>();`	The three data structures are created before the GUI is presented.
`int size()`	Returns the number of elements in the stack.	Returns the number of elements in the queue.	Returns the number of elements in the deque.	Displays the size in the Data area.
`void clear()`	Removes all elements from the stack.	Removes all elements from the queue.	Removes all elements from the deque.	Erases the contents of both the Data field and the data structure display.
`void add(T value)`	Adds an element to the stack, which becomes the new “top” value in the stack. This operation is typically called `push`.	Adds an element to the queue, which becomes the new rearmost value in the queue. This operation is typically called `enqueue` (pronounced “en-Q”).	Adds an element to the rear of the deque.	Displays the new contents of the data structure, with the top or first element as the first line in the display. The Data field is erased.
`void add(T value)`			Also provide a `void addFront(T value)` method to add an element to the front of the deque.
`T peek()`	Returns the top value of the stack; does not modify the stack.	Returns the value at the front of the queue; does not modify the queue.	Returns the value at the front of the deque; does not modify the deque.	Displays the chosen value in the Data field. Displays "`Error`" if the data structure is empty.
`T peek()`			Also provide a `T peekRear()` method to return the value at the rear of the deque.
`T remove()`	Removes and returns the top value of the stack. This operation is typically called `pop`.	Returns and returns the value at the front of the queue. This operation is typically called `dequeue` (pronounced “de-Q”).	Returns and returns the value at the front of the deque.	Displays the removed value in the Data field, and updates the data structure display. Displays "`Error`" if the data structure is empty.
`T remove()`			Also provide a `T removeRear()` method to remove and return the value at the rear of the deque.
`Iterator<T> iterator()`	Returns an iterator for the stack. The iterator should provide values in a top to bottom order.	Returns an iterator for the queue. The iterator should provide values in a front to rear order.	Returns an iterator for the deque. The iterator should provide values in a front to rear order.	The Iterate button puts "`Iterating...`" into the Data field. The Has Next button should display either `true` or `false` in the Data field, and the Next button should display the next value. The Has Next and Next buttons should be disabled (grayed out) until the Iterate button is clicked. To avoid errors, the Next button should be disabled if there is no next item.
`Iterator<T> iterator()`			Also provide an `Iterator<T> reverseIterator()` method.

Implementation

Implement each of these ADTs (Stack, Queue, and Deque) with linked lists. Create and manipulate the lists yourself; do not use any classes from the Java Collections framework, such as Stack or LinkedList. You may, however, use predefined interfaces and Exceptions of the appropriate types. Define each class generically (with a <T> type parameter), so that you can have, for instance, a Queue<Customer> variable.

The Stack class should have a private Node first instance variable, initially null, to point to the first (topmost) element of the stack. The Queue and Deque classes, which need to keep track of both ends of the list, should have private Node front and private Node rear instance variables, initially null.

Each of the three ADT classes should be implemented with two (or three) member classes. (Remember, a member class is the simplest form of inner class.)

Each ADT class should define its own private Node member class. Each Node object will hold one value of the sequence, and link to the next Node in the sequence, thus forming a linked list. Each of Stack and Queue can use a singly linked list; for Deque, however, you will need a doubly-linked list, where each Node contains both a next and a previous link.
Each ADT class should also define a private inner class that implements the Iterator interface; the iterator() method will return one of these objects. The Deque class should define two such iterator classes, one for going forward, and one for going backward.

Why inner classes? There are two reasons:

Most importantly, these are abstract data types. That means you don't want to expose the implementation. Outside your class, nobody should have any access to, or even know about, your Node classes or your special-purpose Iterator classes. This is absolutely critical in large projects.
Inner classes can easily access the private variables of the enclosing class.

Stacks

A Stack can be implemented with a singly-linked list of Node objects. The Stack itself needs only a single instance variable, private Node first, to hold a link to the first (topmost) Node. This link will be null if the stack is empty.

Queues

A Queue can also be implemented as a singly-linked list. But for efficient access, a Queue requires access to both the first and the last element of the sequence. This means you need private Node front and private Node rear fields.

Dequeues

Since you need to be able to add and remove elements at either end, a Deque should be implemented with a doubly-linked list. As with a Queue, you need private Node front and private Node rear fields. Unlike Stacks and Queues, the Deque’s Node class needs a Node previous field in addition to the Node next field.

Hints

When you create the classes you need, such as Stack, be sure to include the <T>, specify the class that it extends (AbstractSequence), and make sure that Inherited abstract methods is checked. If you do this correctly, Eclipse will generate stubs for all the methods and Javadoc comments that you need; you only need to fill them in. For Deque you will need to add some methods manually.

When you declare a type parameter <T>, that type parameter is defined throughout the class, including for the inner classes, so the inner classes can use T but they should not themselves declare a type parameter.

Provided code

Get sequences.zip.

I have written most of the GUI for you, the AbstractSequence class, and a test file for Stacks. StackQueueDequeDisplay is the main program.

You have three basic tasks:

Fill in all the link manipulations in the Stack, Queue, and Deque classes (and test them all with JUnit 4). This is the interesting part of the assignment.
Implement the xxxIterator subclasses in each of the three ADTs. (The Node subclasses are trivial; they have no methods.) The methods in these classes can be tested by testing the Iterator returned by iterator() in the enclosing class.
In the GUI I've filled in the code for only the stackGetSize button. You have to fill in code for the other buttons. This is so that you will look at the GUI code.

Structure of the assignment

Project name: StackQueueDeque
Package name: sequences
Class names and method signatures: Exactly as specified above
Provide Javadoc documentation for all classes and methods, except JUnit tests

Grading criteria

Read the assignment. Do what it says, not something “like” what it says. If anything is unclear, ask. If something is unspecified, do something reasonable.

All classes and methods should have Javadoc comments.

Try to eliminate all warnings that Eclipse gives you. (Generics are especially tricky to get right--usually it's a matter of getting the <T>s in exactly the right places.) Do not suppress any warnings. (Exception: You can do @SuppressWarnings("synthetic-access"); this is just telling you that it’s inserting getter and setter methods for you.)

Due date

Your program is due before 6am Thursday, January 17. Zip up your entire Eclipse project, and submit via Canvas. Only assignments submitted via Canvas will be accepted--any assignments emailed to me will be discarded without comment.

Late penalties

Assignments will be due at 6am precisely. There will be a 10 point penalty (out of 100 points) for programs between one minute and one week late, and a 25 point penalty for programs later than one week. At some unspecified time after one week we will stop accepting assignments.

Because many of you are interviewing this semester, a limited number of 48-hour extensions will be available. To get an extension, email me before 5pm Friday, stating the reason you need the extension. No extensions will be granted after Friday. If you get an extension and fail to get the project in by the extended due date, late points will be counted from the original due date.