CSC 325 Adv Data Structures
Program #2
Jump Tables
For this assignment you are to make a data structure visualizer (similar to the ones I show in class if you’ve had
me before). The idea is that you will visualize 3 data structures: stack, queue, and list. You are to use Java’s
built in Stack, Queue and ArrayList classes. Before I explain much more, here is the output you will be creating
(user input is in bold red, arrows indicate what happens when that user input is submitted (by pressing enter),
and green text and green horizontal line provide content and divide the drawings (and are not actual output)):
1. Stack
2. Queue
3. List
4. Quit
? 1
| |
|—|
| c |
|—|
| b |
|—|
| a |
|—|
1. Push
2. Pop
3. Save & Move to Queue
4. Save & Move to List
5. Quit
? 1 x
| |
|—|
| x |
|—|
| c |
|—|
| b |
|—|
| a |
|—|
1. Push
2. Pop
3. Save & Move to Queue
4. Save & Move to List
5. Quit
? 1 y
When launched the user is
presented with a menu. Typing a
“1” and hitting enter changes to
display a stack (the contents of
which is read from a file, which you
are given)
The user is then presented with
options to modify the stack or save
and move to another data structure.
If “Push” is chosen, a space followed
by a single character should be typed.
This will be what is pushed onto the
stack. The stack is then redrawn.
Here the user is attempting to push
‘y’ onto the stack.
| |
|—|
| y |
|—|
| x |
|—|
| c |
|—|
| b |
|—|
| a |
|—|
1. Push
2. Pop
3. Save & Move to Queue
4. Save & Move to List
5. Quit
? 2
| |
|—|
| x |
|—|
| c |
|—|
| b |
|—|
| a |
|—|
1. Push
2. Pop
3. Save & Move to Queue
4. Save & Move to List
5. Quit
? 3
| a | b | c |
1. Enqueue
2. Dequeue
3. Save & Move to Stack
4. Save & Move to List
5. Quit
? 1 !
Selecting “Pop” will pop from the
stack and redraw. No other input
from the user is required if they
want to pop
Selecting one of the “Save & Move”
options will save the stack contents
back to the file. This means if the user
re-launches the application or
navigate back to the stack, the file
will be read again and the altered
contents from last time will be there.
Just like with the stack, when you
select “Enqueue” you should give a
character along with it. This may be
any single character. The queue is
then redrawn. Similarly, selecting
‘Dequeue’ will dequeue the front
number.
| a | b | c | ! |
1. Enqueue
2. Dequeue
3. Save & Move to Stack
4. Save & Move to List
5. Quit
? 3
| |
|—|
| x |
|—|
| c |
|—|
| b |
|—|
| a |
|—|
1. Push
2. Pop
3. Save & Move to Queue
4. Save & Move to List
5. Quit
? 4
{ a, b, c, }
1. Append
2. Remove
3. Save & Move to Stack
4. Save & Move to Queue
5. Quit
? 1 8
Selecting “Save & Move” saves the
queue to the queue file so it can be
retrieved later. Here we are
jumping back to the stack.
As you can see, our stack was
preserved from last time. Now let’s
move to the list.
Lists are shown with curly braces and
commas between numbers. Selecting
‘Append’ requires the character to
add just like the others. Recall that
single digit numbers can be
considered characters as well.
Selecting ‘Remove’ will remove the
number at the end of the list.
Selecting any ‘Save & Move’ will save
the list to the list file.
{ a, b, c, 8, }
1. Append
2. Remove
3. Save & Move to Stack
4. Save & Move to Queue
5. Quit
? 5
Selecting “Remove” will remove
the number 4. But here I am
showing that we can quit the
application. All menus have this
option. This merely exits the
application and doesn’t clear the
screen beforehand.
A few constraints:
• Assume the user will put a single space followed by a single character if adding to the data structure is
chosen (i.e. push, enqueue or append). Remember that not all menu options require more input from
user, so only scan for the extra character when it is expected.
• You must read from the appropriate files when a view switches to a particular data structure. And you
must write the new data back to the file when the view switches to something else.
• You must use Java’s generic Stack, Queue, and ArrayList classes to store data and use Java’s HashMap
class for your jump tables. And you must provide an appropriate generic type parameter (use
“Character” for your data) where appropriate. Any use of “raw types”1 will lower your grade as this is
considered by most developers to be bad practice.
1 Google search this to see what I mean if you’ve never heard this term before
Empty Data Structures:
If the user selects “Pop”, “Dequeue” or “Remove” and the corresponding data structure is empty, the
operation should effectively do nothing. The user should then be presented with the same options as before.
This may mean that you need to check if the data structure is empty and not run the operation if it is, or you
may use different operations that won’t crash the program if the data structure is empty (refer to Java
documentation to see what I mean, for example there is more than one method for removing from a Queue).
| |
|—|
1. Push
2. Pop
3. Save & Move to Queue
4. Save & Move to List
5. Quit
?
|
1. Enqueue
2. Dequeue
3. Save & Move to Stack
4. Save & Move to List
5. Quit
?
{ }
1. Append
2. Remove
3. Save & Move to Stack
4. Save & Move to Queue
5. Quit
?
Empty stack Empty queue Empty list
Granted this may not be the best way to present these data structures as empty, so feel free on this one part
to draw the empty data structures how you see fit (but you should draw something at least).
Finite State Machines:
You must use a finite state machine to code this application and have three jump tables, one for when we
enter a state, one for when we stay in a state and one for when we exit a state. So you will need an enum for
the states, i.e.:
enum State {
IDLE,
STACK,
QUEUE,
LIST
}
And inside of your Screen class (more on this below), you will need the HashMap objects (i.e. our jump tables):
private HashMap<State, StateEnterExitMeth> stateEnterMeths;
private HashMap<State, StateStayMeth> stateStayMeths;
private HashMap<State, StateEnterExitMeth> stateExitMeths;
Notice that we are using two different types of methods. The first, StateEnterExitMeth is for entering and
exiting a state. Create this as an interface and make the invoke function take no parameters and not return
anything (i.e. it should be void). The second, StateStayMeth, is for our stay methods. This should be made into
a separate interface where the invoke method in this returns a boolean (but still has no parameters). The
reason for this is so we can track if the user selects “Quit” in any of the menus. When this happens, the
corresponding state stay method can return false. Otherwise it should return true. To help with this, this is
what the main class and main method should look like:
public class JumpTableMain {
public static void main(String[] args) {
Screen screen = new Screen();
boolean keepRunning = true;
while(keepRunning) {
keepRunning = screen.doState();
}
}
}
As you can see, the “doState” function (similar to the lecture notes) should grab the current state stay method
and invoke it. It should then return what that method returns. If it returns false, the loop in main exits. If it
returns true, we stay in the loop and doState is called again. Essentially we are trapped in an infinite loop until
the user selects “Quit” in any of the menus.
Classes and Other Data Types:
For this assignment, you will need to create the following:
• An interface called StateEnterExitMeth
o This contains a single method called invoke that doesn’t receive any parameters and doesn’t
return anything
• An interface called StateStayMeth
o This contains a single method called invoke that doesn’t receive any parameters but does
return a boolean result
• An enum called State
o This contains all of the states our application can be in (see above)
• A class called Screen
o This will be where the bulk of the application code is. This will contain the three jump lists, the
data structures (ArrayList, Stack and Queue), and the current state of the application.
o It will also contain all state methods that will draw each data structure, load and save them
from/to their respective files, draw each menu, and carry out the operations for each data
structure as they are selected from the menu
• A public class called JumpTableMain
o This will contain our entry point (see above)
Important:
It is natural for you to be confused about this assignment. There is a lot going on and a lot of new things are
happening here. I strongly encourage you to read and re-read this assignment and then go back and read and
re-read the lecture notes on this. When presented with a project in the real world, part of that project is to
fully understand what it is you are doing. This takes a bit of time and you are unlikely to understand
everything right away. Just remember to break the project down into tiny chunks and work on them one at a
time, ensure they work before moving to the next chunk. If you try to do too many things at once, you will fail.
You might want to start by thinking of what should be the responsibilities of the enter and the exit methods.
What should enter, stay and exit do for each of the data structures.
File I/O:
You are given three files for this assignment, “stack.txt”, “queue.txt”, and “list.txt”. The files all start with the
same data, i.e. “a,b,c,”. Yes, the comma at the end is purposefully there. This will make it easier for you to
read the contents and not have to handle the special case of the last character not having a comma after it.
When you write to the file, the trailing comma should be written. You are to read in the file using file i/o in
Java. You may have to Google search this as I suspect most of you have never done this type of thing. Don’t
worry, Java makes it pretty easy to read and write to/from a file as there are a few classes built in to
accomplish this (each with their own pros and cons, pick whichever one works for you).
Coding Style:
Just getting an application to work correctly is not everything. It must also look good! Remember that in
industry, you rarely work alone. If your code is sloppy and doesn’t use best practices, your application will be a
nightmare to maintain and update, and fellow developers will not enjoy working with you. For this reason, I
don’t want to see any hard-coded literals (e.g. the file names should be constants in the class that you refer
to) and you should absolutely create helper functions that are called from your state methods. Function to
grab the character to add to the data structure from the user input, function to clear the screen, function to
load a data structure from its corresponding file, save a data structure’s content to its corresponding file,
drawing the data structure to the screen, drawing the menu for that data structure, and any other helper
methods you think you will need. Remember the D.R.Y. principal (i.e. “Don’t Repeat Yourself”). If you find
yourself writing the same logic twice or more, you should consider making a helper function for this. This can
also help to make things such as redrawing the data structure after a “push”, “pop”, “enqueue”, “dequeue”,
“append” or “remove” a lot easier.
You should also be putting thought into the order of your methods. Similar methods should be next to each
other. Personally I put extra blank lines between groups of methods. For example, I put all of my StateEnter
methods (StateEnterIdle, StateEnterStack, StateEnterQueue, and StateEnterList) with no blank lines between
them but then put a blank line before the next group. In other words:
/// ENTER
private void StateEnterIdle() {
}
private void StateEnterStack() {
}
private void StateEnterQueue() {
}
private void StateEnterList() {
}
/// STAY
private boolean StateStayIdle() {
}
private boolean StateStayStack() {
}
private boolean StateStayQueue() {
}
private boolean StateStayList() {
}
/// EXIT
private void StateExitIdle() {
}
private void StateExitStack() {
}
private void StateExitQueue() {
}
private void StateExitList() {
}
I then collapse them by pressing alt+2 (on the numpad above the letters) in Notepad++. You could also put a
single blank line between functions in a group and put two blank lines between groups. However you want
your code to look, as long as it is consistent and easy to find things.
Bonus:
You are given a mysterious file called Bonus.class. For this assignment to run correctly, you will need to
compile and run your code on a linux-like terminal such as Git Bash. Make sure the Bonus.class file is in the
same directory as your JumpTableMain.java file. Add a call to the static method “check” from the Bonus class
after drawing the menu to the screen. Do this for stack, queue and list. Send the function the appropriate data
structure. For example, right after drawing the stack menu, add the following code:
Bonus.check(stack);
This assumes your Stack variable is called “stack” (change it to whatever your Stack variable is called if not).
Right after drawing the queue menu, you should have: Bonus.check(queue); And right after drawing
the array list menu, you should have: Bonus.check(list); To reveal the bonus, just think of what you
want and write it into the data structure ?
For submission:
Submit your .java file (everything should be in a single file) to Moodle.
Rubric:
# ITEM POINTS
1 Stack works 8
2 Queue works 8
3 ArrayList works 8
4 Uses Java’s built in data structures 5
5 Starting menu is correct 2
6 User can quit from any menu 2
7 Output is formatted as sample output shows 2
8 File I/O works correctly 5
9 State machine done correctly 5
10 State enter, stay and exit methods are correct 5
TOTAL 50
Penalties:
# PENALTIES POINTS
1 Doesn’t compile -50%
2 Doesn’t execute once compiled (i.e. it crashes) -25%
3 Late up to 1 day -25%
4 Late up to 2 days -50%
5 Late after 2 days -100%
Note that the penalties show automatic point loss, however some issues (such as not compiling) might cause a
cascade of points to be loss from the inability to test/execute other parts of the application. In other words,
don’t give me code that doesn’t compile. You might lose a lot more than 50%.
