Stacks and Queues

CS 206 - Introduction to Data Structures

Homework 5

Stacks and Queues

Due Thursday, March 5 prior to 11:59PM

Jen and Jill

Jen and Jill love jumping (they really do). Sometimes forward, sometimes backward. When jumping forward, Jen puts her jumps on a stack. When backward, she pops her stack for the backward distance. (If Jen wants to jump backward but her stack is empty, she does not move.) Jill puts her forward jumps on a queue. When jumping backward, she polls the queue for the backward distance. Similar to Jen, Jill does not jump backward when her queue is empty.

For this homework you will write simulators for Jumping Jen and Jumping Jill.

Copy Jumper.java from /home/gtowell/Public206/a5 into a directory for this assignment. Use the function jump in the Jumper class to determine the direction and distance of Jen and Jill's jumps. (As documented in the Jumper class, -1 means jump backward; a posivive number indicates the distance to jump forward.)

Write a linked list based implementation for stack and queue using the stack and queue interfaces discussed in class. You might start from the single linked list or double linked list code from lecture (or you could start with a clean sheet of paper). The interface definitions and the linked list code are all available on the class website. Whatever the way in which you implement your underlying linked list, be careful that there is no duplicated functionality between your linked list and your stack/queue. Also, the push, pop, and peek operations of stack and the offer, poll and peek (and add, remove and element) operations of queue must all run in O(1) time. Be careful not to have information stored in more than one place. For instance, the linked list class and the stack class both have a variable for size.

Use your stack and queue implementations to build simulators for Jen and Jill in which they make 100,000 jumps. With those simulators record (for instance in an array) their distance from the start after every jump.

Using the record of jumps, write code to answer the following questions for both Jen and Jill (put your answers in the README in a section labeled something clever like "Jen and Jill"):

The maximum distance away from the start they get
Their final distance away from the start.
The average distance they are from the start
The most common distance from the start (the modal distance)
The number of different distances from the start the jumper occupies at some time in their 100,000 jump history

Run you program several times. Answer the questions above based on the average of several runs. (You may hand collect data to compute these averages.) Using these averages, answer one final question

Are any of the answers to the above questions meaningfully different for Jen and Jill? If yes, which ones? Speculate on why the differnce occurs, or on which there are no interesting differences.

Class Structure

One final requirement. Jen and Jill are both jumpers. So design a class JumpingPerson that Jen and Jill each extend. Put into your JumpingPerson class all code that Jen and Jill share.

You might contend that Jen and Jill are first a Person and then a Jumping Person, and so you should also have a Person class. This is true, and if you want to go there; great. However, it is not required.

Development Suggestions

These are suggestions not requirements.

Develop the link-based stack and queue first. Write a main method in each that tests its functions along the lines of the main methods discussed in lecture. That way, when you go to use these classes in Jen and Jill you are confident that they already work correctly.

After getting your stack and queue working, develop Jen or Jill without the JumpingPerson class. Suppose Jill. Get Jill working correctly. (At this point you would have something you could submit for a good portion of the credit of the assignment). Then anaylse Jill for what code can be shared with Jen. Move all of that shared code up to JumpingPerson. Make Jill extend JumpingPerson, delete all the code you moved up, and ensure Jill still works. Then finallly develop Jen. (This might be referred to as a form of "bottom-up" development, whcih is definitely not the top-down development approach you might have learned elsewhere. A mix of top-down and bottom-up uually works well for me.)

Another suggestion. Get Jill working with only 10 (or even 5) jumps. Use the debugger in VSC to step through literally every line of code; checking the value(s) of all variables. In this way you can ensure that the code does exactly what you intend for it to do. (It may still not be correct, but at least it is doing what you want.)

Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer.

README: This file should follow the format of this sample README (https://cs.brynmawr.edu/cs206/README.txt)
Answers to the questions posed above. This should be within the README, but it is acceptable as a separate, text, file
Source files: Every .java file used in the final version of every part of your project (including the imported files)
Unique Data files used: This is expected to be blank as the only data files you should use are as above. However, you could use a data file (or two) as a part of your test driver class (I do not recommend this, I simply note that you could).

DO NOT INCLUDE:

Data files that are read from the class site.

The following steps for submission assume you created a folder named AssignmentN in the directory /home/YOU/cs206/ and that folder contains all of your code.

For this assignment N=5
Put the README file into the project directory (/home/YOU/cs206/AssignmentN)
In the README, include all of the data requested above for Jen and Jill and a brief discussion of the data (answering at least the two posed questions).
Go to the directory /home/YOU/cs206
Enter submit -c 206 -p N -d AssignmentN

For more on using the submit script click here