Assignment 2

Assignment 2: Generic Stacks and Queues

CS102: Data Structures, Fall 2013

Eric Koskinen and Daniel Schwartz-Narbonne

New York University

Due: 4:55PM (16:55:00), Friday October 4th

Clarification

As discussed in class, the stacks and queues should be implemented using linked lists. You are responsible for creating the linked list node class, and using it to implement the stacks and queues. Hint: you should be able to reuse much of your code from Assignment 1. We have updated the submission and compilation guidelines to reflect this, and apologize for any confusion.

Context

Your mobile app for movies has recently been extended and two critical components are needed:

Part A. To handle inbound data, a FIFO (first-in,first-out) Queue is needed. There are several places where queues are needed and each involves data of different types, so the Queue must be generic.

Part B. A facility has been added to permit users to input strings of movies in groups for various purposes. For example, they may input a string such as:

[Drama (`Casablanca', `Lawrence of Arabia')], [Action (`Die Hard')]

Or input strings such as:

{Casablanca[Bogart,Bacall] (1945)}

The precise formatting of the input strings does not matter to you. Your task is simply to determine one thing: whether an input string is balanced. A string is balanced provided that for every occurrence of an opening character (,{,[,<, or ` there is corresponding closing character ),},],>,or ' and a new nesting levels close in the reverse order that they were opened. The above strings are all balanced. Recall also the examples from the lecture notes:

{[CS](102)} - balanced
{[CS(102)]} - balanced
{[CS(102])} - unbalanced
{[CS(102)] - unbalanced

Notice that checking whether a string is balanced can be implemented with a Stack. The algorithm is as follows:

Balance Checking Algorithm

1. Create a stack of characters

2a. Scan through the strange, character by character

When an open character (,{,[,<,or ` is observed, push the character onto the stack

2b. When a close character ),},],>,or ' is observed, pop a character from the stack and ensure that it is the open-counterpart to the close character (if not, the string is unbalanced!.

3. At the end of the string, if the stack is empty, the string is balanced.

Scope

This assignment consists of the following tasks:

List-based implementation of a Stack (class StackList)
Testing your StackList implementation
List-based implementation of a Queue (class QueueList)
Testing your QueueList implementation
Implementation of application class BalanceCheck, which must use your StackList implementation to determine whether input strings are parenthetically balanced.

Interfaces and Classes

We have provided the following interface files, as well as some example code, as follows:

Collection.java -- The standard interface for a Collection. This has been implemented for you.
Stack.java -- The interface for a Stack. This has been implemented for you.
Queue.java -- The interface for a Queue. This has been implemented for you.
StackList.java -- A template for your StackList. You will need to implement this class.
QueueList.java -- A template for your QueueList. You will need to implement this class.
BalanceCheck.java -- A template for the BalanceCheck class. You will need to implement this class.

Testing

As with all assignments, you will use the test-driven design approach. There is also a suite of testing tools that you will need to extend for this assignment.

TestHarness.java -- A TestHarness class which provides the infrastructure for the testing suite. You do not need to modify this class.
Test1.java, Test2.java, ... -- These classes are examples of tests. You will need to create more of them, one for each type of test. New classes must then also be registered by updating Test.java. Your tests must include:

Tests for StackList
Tests for QueueList
Tests for BalanceCheck

Test.java -- The main test function which registers individual tests and then invokes all of them. You will need to extend main in this class.

As with the previous assignment, we will be developing some incorrect implementations, and running your tests cases on them. One of the jobs of your test suite is to try to catch all of our broken implementations.

Implementation

Your implementation of the QueueList<E> class involves the following methods, all of which should be implemented using recursion, not iteration. Your code should gracefully handle cases with null variables, and should never crash.

E dequeue() -- Removes and returns the oldest value.
enqueue(E el) -- Adds value el to the queue.

int size() -- Returns an integer representing the current size of the Queue.
boolean isEmpty() -- Returns true if and only if the Queue is empty.
String toString() -- converts the set into a string using precisely the following format (our automated tests will testing this method by comparing its output strings against correct strings, and hence this method will only pass these tests if every character is the same).

IN -> [ “data 1” , “data 2” , “data 3” ] -> OUT

where “data 1”, “data 2”, “data 3” are the current elements of the queue, printed via the data elements’s ToString() method.

void PrettyPrint() -- Displays the entire Queue on the console/terminal. Hint: use toString() as a helper function.

Your implementation of the StackList<E> class involves the following methods. Your code should gracefully handle cases with null variables, and should never crash.

E pop() -- Removes and returns the most recently added value.
push(E el) -- Adds value el to the Stack.

int size() -- Returns an integer representing the current size of the Stack.
boolean isEmpty() -- Returns true if and only if the Stack is empty.
String toString() -- converts the set into a string using precisely the following format (our automated tests will testing this method by comparing its output strings against correct strings, and hence this method will only pass these tests if every character is the same).

TOP: [ “newest” , “old” , “older” , “oldest” ]

where “newest” , “old” , “older” , “oldest” are the current elements of the stack, printed via the data elements’s ToString() method.

void PrettyPrint() -- Displays the entire Stack on the console/terminal. Hint: use toString() as a helper function.

Compilation and Execution

Your assignment will be automatically compiled as follows:

javac *.java

Note that the Java compiler will automatically compile other classes that are inherited. Finally, your code will be executed as:

java Test

Note that your implementation will be built and executed against your test cases, as well as our test cases. It is to your benefit to devise as many test cases as possible!

Submission

Please submit the following files to NYUClasses:

Your StackList.java implementation.
Your QueueList.java implementation.
Your BalanceCheck.java implementation.
Each TestX.java test class (where X is some positive integer).
Any other files you create to implement the linked list (e.g. ListNode.java)

Grading

Your assignment will be evaluated based on the following:

Sufficiency of the tests you design (33%)
Correctness of the implementation (33%)
Clarity and organization of the code, and sufficiency of comments (34%)

We look forward to your submission!

-- CS102 Course Instructors

Bonus question (mandatory for Honours students)

Implement the Stack and Queue using Ocaml’s built in lists.