Assignment 2 Data Structures

University of Canberra 
Faculty of Science and Technology  
Software Technology 2  
Assignment 2 – Data Structures 
Individual assignment 

Problem 1 [2 marks]  Sort Stack

Problem 3.5, page 99 in Cracking the Coding Interview

Question: [1.5 marks] Complete the method sortStack to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you cannot copy the elements into any other data structure (such as an array, a list, etc.). Use the methods from class java.util.Stack only—the stack supports the following operations: push, pop, peek, search, and isEmpty.

• The input [0.5 marks]: Add at least two input instances in the main method to test your sortStack
• No requirements on output formats.
• Submission: Copy your entire Java program to your word file for submission.

import java.util.Stack; 	 
public class StackQuestion { 
public static void main(String[] args) { 	 

// The test cases 	 
} 

// TODO Complete the sortStack method to sort the input stack 
public static Stack sortStack(Stack input) { 	 
// Add your code here to sort Stacks such that 
// the smallest items are on the top 	 
} 
} 

Problem 2 [2 marks] Hash Table/Hash Map Solve the following problem on the Hacker Rank website: Ransom Note

(https://www.hackerrank.com/challenges/ctci-ransom-note/problem)

• You are required to use HashTable or HashMap to solve this problem.
• You need to log-in to access all the 21 test cases for this problem on the website.
• Submission: Copy your entire Java program to your Word file for submission. Also add a note to show how many test cases your program could pass.

Problem (copied from the Hacker Rank website)

Problem 3 [8 marks] Snake Game

Snake (also called Nibbles) is a classic game which is played on a rectangular game board. When the game starts, an apple is randomly added to the game board and the snake moves forward. The player uses the 4 arrow keys on the keyboard to change the current direction of the snake. When the snake eats the apple, the body of the snake grows longer, and another apple is randomly added to the game board. The game is over if the snake either runs into one of the 4 edges of the game board, or it runs into its own body. 

In this project, you will modify the existing Snake game implemented by Jan Bodnar and available at https://github.com/janbodnar/Java-Snake-Game to gain experience with linked list data structures.

This game program uses two arrays below to store the x and y coordinates of all joints of the snake: 

private final int x[] = new int[ALL_DOTS]; private final int y[] = new int[ALL_DOTS];

You are required to remove these two arrays from the game program and implement

SnakeLinkedList and SnakeNode classes to perform the tasks of these two arrays. Other existing variables and method names in the game program are unchanged (however some method bodies that contain the x and y coordinates can be modified).

The SnakeLinkedList class is either singly-linked list or doubly-linked list class. This class contains the basic variables and methods for a linked list and the snakeMove method to move the snake. You cannot use the existing LinkedList class in Java to implement this class. 

The SnakeNode class contains the basic variables and methods for a linked list node, the x and y coordinates and colour (red, green, yellow or blue). The red head and joints on the body of the snake are instances of this SnakeNode class. Below are screenshots that show the required snake with a red head and joints on its body when it starts and after it eats apples.