Project 02: Data Types

Individual, Due: 2025 Sep 30, 11:59pm

In this assignment, you will implement a variety of data types, each with their own strengths and limitations. You will also learn about generics, iterators, and throwing exceptions.

NOTE: Not only should your implementation work correctly, but it will need to use space and time efficiently to receive full credit.

This assignment is based on web exercises from the Algorithms 4/e book website.

The `Steque` Class

A stack-ended queue, or steque, is a data type that supports the operations push, pop, and enqueue. Donald Knuth calls it an output-restricted deque. In other words, a steque allows for data to be added to either end (top with push, bottom with enqueue) but removed from only one end (top with pop). The figure below provides an illustration of the manipulation operations of a steque.

Implement a generic steque using a singly-linked list to fulfill the basic API below.

Steque is the constructor. size returns the number of items stored. isEmpty returns true iff steque is empty. enqueue enqueues item to bottom of steque. push pushed item to top of steque. pop pops and returns top item. iterator (a method of Iterable interface that must be implemented in Steque class) returns new Iterator<Item> that iterates over items in steque.

Edge Cases: Throw a NoSuchElementException if the pop method is called on an empty steque.

Performance Requirements: Your implementation for each of the operations should take constant time in worst case (not amortized) and use space linear to the number of elements in the steque.

Loitering Prevention: Be sure to prevent any data loitering!

Iterator: The iteration order can be any order, but it should be efficient (next and hasNext should take constant time) and touch each Item currently on the Steque exactly once. The iterator should throw a ConcurrentModificationException if the next or hasNext methods are called after the steque has been modified (push, enqueue, pop). Handling the latter case is not difficult, but it may take some thinking. The iterator should throw a NoSuchElementException if next is called when there is nothing left to iterate over (hasNext()==false). Your iterator can have an empty implementation for the remove method.

The `MinimumStack` Class

A minimum stack adds to the functionality of a stack a constant-time method for retrieving the minimum value stored. Implement a generic minimum stack to fulfill the basic API below. You may assume that the items are Comparable (MinimumStack<Item extends Comparable>), and your implementation may use the Stack data type from the provided algs4.jar library.

MinimumStack is the constructor. size returns the number of items stored. isEmpty returns true iff stack is empty. push pushes item onto top of stack. pop pops and returns the top item. minimum returns the minimum item in constant time. iterator returns new Iterator<Item> that iterates over all items. compareTo returns an integer representing the comparison of this to other (ex: in thing1.compareTo(thing2), this is thing1 and other is thing2), where 0 indicates the two Items are equal in value, a negative number (not necessarily -1) indicates that this is less that other, and a positive number (not necessarily 1) indicates that this is greater than other.

Edge Cases: Throw a NoSuchElementException if the pop or minimum methods are called on an empty stack.

Performance Requirements: It is easy to implement the minimum method to take linear time, but this is not efficient enough. Your implementation for each of the operations must take constant time in the worst case (not amortized) to receive full credit.

Loitering Prevention: Be sure to prevent any data loitering!

Iterator: The iteration order can be any order, but it should be efficient (next and hasNext should take constant time) and touch each Item currently on the MinimumStack exactly once. The iterator should throw a ConcurrentModificationException if the next or hasNext methods are called after the stack has been modified (push or pop). Handling the latter case is not difficult, but it may take some thinking. The iterator should throw a NoSuchElementException if next is called when there is nothing left to iterate over (hasNext()==false). Your iterator can have an empty implementation for the remove method.

The `OnePointerQueue` Class

Queues implemented using singly-linked lists typically maintain two "pointers", one for each end. Implement a queue that maintains only one "pointer" and fulfills the basic API below.

OnePointerQueue is the constructor. size returns the number of items stored. isEmpty returns true iff queue is empty. enqueue enqueues item to "back" of queue. dequeue dequeues and returns item from "front" of queue. iterator returns new Iterator<Item> that iterates over items.

Edge Cases: Throw a NoSuchElementException if the dequeue method is called on an empty queue.

Performance Requirements: All of the operations must take constant time in worst case (not amortized) to receive full credit.

Hints: Use a circular linked list and maintain a pointer to the last item. Implement a toString function that creates a String representation of the linked list to help with debugging.

Loitering Prevention: Be sure to prevent any data loitering!

Iterator: The iteration order can be any order, but it should be efficient (next and hasNext should take constant time) and touch each Item currently on the OnePointerQueue exactly once. The iterator should throw a ConcurrentModificationException if the next or hasNext methods are called after the queue has been modified (enqueue or dequeue). Handling the latter case is not difficult, but it may take some thinking. The iterator should throw a NoSuchElementException if next is called when there is nothing left to iterate over (hasNext()==false). Your iterator can have an empty implementation for the remove method.

External

For this assignment, the only library functions you may call are those in stdlib.jar and algs4.jar. Do not import any other packages, and do not call any other library functions except those specified above.

You will need to use java.util for exceptions and iterator, but do not use it for any data structure. For example, the top of your code can include the following, but nothing else.

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

Testing

Programmers often assume their code is correct, but bugs are crafty and difficult to spot. Good programmers test their code often to verify its correctness.

In fact, there is a software development approach called Test-driven Development (TDD), where programmers write the tests first (before coding starts!), and then they start implementing functions and features to until tests begin to pass. Once all tests pass, the code is considered finished. Bugs exist in the codebase if and only if a test was missing that tests for that bug. If a bug is found, programmers first write a test to detect the bug, then they write code to pass the test. Any time a new feature is added or code is updated, the changes are automatically rejected from being included in the main branch if any test fails.

We will not adopt TDD in this class, but it is still good to learn how to write tests. The autotester does a fairly good job at checking your code, but it only runs once a day. Also, it gives only some feedback, but it does not tell you all the information about why a test failed. You are strongly encouraged to start creating your own tests.

Tester Feedback #

Below is a gist of some of what the tester is doing, which can give you some insight into reading the tester feedback. You are welcome to duplicate these tests in your own code (see next section), but you should also think up other tests to run.

Steque: correct

push, pop
1. check that steque is empty
2. push on two items
3. check steque size is 2
4. pop one item and make sure it is the correct item
5. pop one item and make sure it is the correct item
6. check that steque is empty again
7. repeat
size, isEmpty
1. check that size and isEmpty return correct values after either pushing, popping, enqueueing
enqueue, pop
1. same as push, pop above, but using enqueue

MinimumStack: correct

push, pop
1. same as push, pop for Steque
minimum different
1. pushes on a bunch of different numbers, checking minimum each time
2. pops off the numbers, checking minimum each time
3. repeat

OnePointerQueue: correct

enqueue, dequeue
1. same as enqueue, pop for steque

Steque / MinimumStack / OnePointerQueue: efficient

these tests involve inserting (pushing, enqueuing) and removing (popping, dequeueing) a bunch of times to make sure your implementation does not take too long
also, size, isEmpty, and minimum (MinimumStack only) are tested, too

Edge Cases

For each of the data types, the tester checks whether your implementation throws the correct Exception when it should and does not throw an Exception when it should not.

Iterators

For each of the data types, the tester checks that your implementation iterates over the items that have been inserted (and not yet removed)
Also, the tester checks that your implementation throws the correct Exception if the data structure has been modified while iterating

Writing Your Own Tests

You are encouraged to write code to test your own implementations. You can add this testing code in the main function. As your tests get longer, you might want to consider refactoring the tests into separate functions and then call them from main.

Another a common command used to make sure your code is behaving correctly or to ensure that invariants remain true is with the assert statement. The assert statement is special command that will throw an AssertionException whenever a condition is false.

Important

Java will only execute assert statements if the assertions are enabled using the -ea virtual machine (VM) option. Otherwise, ALL assert statements are ignored.

To enable assertions in the VM, edit the project's configuration, click Modify options dropdown, click Add VM options, then type -ea in the newly added VM options textbox. See the assert docs for more details.

Below is an example snippet using assert.

public static void example_tests() {
    MinimumStack<Integer> ms = new MinimumStack<>();

    // a brand new MinimumStack _should_ be empty and have no items!
    assert ms.isEmpty();                     // should be empty
    assert ms.size() == 0;                   // should have no items

    // once we push an item, we _should_ have exactly one item
    // and the minimum _should_ be that value we just pushed
    ms.push(2);
    assert !ms.isEmpty() && ms.size() == 1;  // exactly one item on stack
    assert ms.minimum() == 2;                // make sure 2 is min

    // if we push a bigger item, the minimum _should_ not change
    ms.push(4);
    assert ms.minimum() == 2;                // make sure 2 is still min

    // make sure items are popped off in the correct order (LIFO)
    Integer v = ms.pop();
    StdOut.println("Just popped " + v);
    assert v == 4;                           // make sure 4 was popped
    v = ms.pop();
    assert v == 2;                           // make sure 2 was popped
}

public static void main(String[] args) {
    MinimumStack.example_tests();
}

Warning

Note how the code stores the result of pop() in a variable (line 19 and 22), then tests if the popped value is correct (line 21 and 23). If the code was assert ms.pop() == 2; instead, then disabling assertion tests (no -ea VM option) would cause pop() not to be called. This is important to note when your asserts are intermingled in with real code (not just test code).

Submission

You will need to implement several data structures in MinimumStack, OnePointerQueue, and Steque and perform memory analysis.

Files

The diagram below indicate which files you can edit, which files/folder you should not edit, and the rest are files/folders that might be changed by IntelliJ or git but you should not change directly.

P02_DataTypes/...
 ├─ P02_DataTypes.iml
 ├─ .idea/...
 ├─ .git/...                    <- **DO NOT EDIT**
 ├─ .gitignore                  <- **DO NOT EDIT**
 ├─ .gitmodules                 <- **DO NOT EDIT**
 ├─ out/...
 ├─ libs/...
 ├─ src/...
 │   ├─ MinimumStack.java       <- Java file that you might need to modify
 │   ├─ OnePointerQueue.java    <- Java file that you might need to modify
 │   └─ Steque.java             <- Java file that you might need to modify
 ├─ data/...                    <- Additional test input files you create
 ├─ data_ref/..                 <- **DO NOT EDIT**
 └─ readme.md                   <- Fill this out before submission!

We will supply an IntelliJ project with stdlib.jar and algs4.jar libraries. These libraries contain many useful classes.

Submission

Once you have completed the assignment requirements, simply stage, commit, and push your changes to the CSE GitLab, and then close the issues.

Do NOT submit anything to the course Brightspace page.

Grading Rubric


	Implementation Correctness
3pts	Correct implementation of `Steque` (except edge cases)
3pts	Correct implementation of `MinimumStack` (except edge cases)
3pts	Correct implementation of `OnePointerQueue` (except edge cases)
3pts	Correct iterator implementation for all three classes
	Implemantation Performance and Conformance
3pts	Efficient implementation of `Steque` (only if ≥2pts Correct)
3pts	Efficient implementation of `MinimumStack` (only if ≥2pts Correct)
3pts	Efficient implementation of `OnePointerQueue` (only if ≥2pts Correct)
6pts	Meets conformance requirements (API + Exceptions)
	Documentation
3pts	Completed `readme.md`
3pts	Reasonable memory analysis

Project 02: Data Types

Individual, Due: 2025 Sep 30, 11:59pm

The Steque Class

The MinimumStack Class

The OnePointerQueue Class

External

Testing

Tester Feedback #

Writing Your Own Tests

Submission

Files

Submission

Grading Rubric

The `Steque` Class

The `MinimumStack` Class

The `OnePointerQueue` Class