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

Purposes of this assignment

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:

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

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.

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.

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.)

Why inner classes? There are two reasons:

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.
singly-linked list

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.

As always, Eclipse will generate stubs for all the Javadoc tests you need.

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:

Structure of the assignment

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. All exposed (non-private) methods must be tested with JUnit4 tests.

Throw the right exceptions in the right places. Your JUnit tests should test that they are thrown as appropriate.

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 Tuesday, January 24. Zip up your entire Eclipse project, and submit via Blackboard. Only assignments submitted via Blackboard will be accepted--any assignments emailed to me will be discarded without comment. A late penalty of 5 points per day (out of 100 points) will apply.

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.