CS 245 – Practice Assignment 6 Fall, 2019
Practice Assignment 6 – Palindromes
The goal of this assignment is to practice the implementation of two of the data structures we’ve seen:
Stacks and Queues. For this assignment, the correctness of the data structures is primarily measured by
how well the structures can be used to detect palindromes.
Two of the data structures we discussed are Stacks and Queues. A Stack is a LIFO data structure which
has four required functions (push, pop, peek and empty). On the other hand, a Queue is a FIFO data
structure which has three functions (enqueue, dequeue and empty). Because of the order in which data
is placed in these data structures, they can be used to detect palindromes.
A palindrome is a word which can be written the same way backwards or forwards. For example, the
reverse of the word “level” is the same word. (In addition, phrases such as “Al lets Della call Ed Stella” are
palindromes, if spaces omitted and uppercase letters changed to lowercase. But we don’t test for those.)
If an input string is copied, letter-by-letter, into a Stack instance (with a push operation) and to a Queue
instance (with an enqueue operation), the output order should match for palindromes. However, the same
should cause a mismatch for non-palindromes. For example, a non-palindrome word such as “rat” placed
into a Queue instance is retrieved in order (r – a – t) but for a Stack instance, the order is reversed (t
– a – r).
Requirement 1: Get the files you need. You will copy them to your own GitHub repository using the
1. Log into GitHub. If you do not have a GitHub account, create one via github.com > Sign Up.
2. Point your browser to the URL https://classroom.github.com/a/oK6389rm.
3. If necessary, authorize GitHub Classroom by selecting the “Authorize github” button.
4. If available, select your name from the list of names available. This will link your GitHub ID.
5. Accept the assignment by selecting the appropriate button.
If successful, your repository should contain three (3) Java files:
● Practice06Test.java — the main file
● Queue.java — the interface for the Queue implementation
● Stack.java — the interface for the Stack implementation
Requirement 2: Add to the code in order to make it run. Specifically, you must add two classes:
ArrayQueue.java and ArrayStack.java. ArrayQueue must implement the interface defined in the file
Queue.java, specifically the functions: enqueue, dequeue and empty. ArrayStack must implement the
interface defined in the file Stack.java, specifically the functions push, pop, peek and empty. Each of the
implemented data structures is required to use an array implementation for storing data, as discussed in
class, with a default array size of 10 instances of some template type, T, passed at time of declaration.
The implementations are additionally required to grow to double the current size when an attempt is made
to exceed the size of the arrays.
Two implementation tips are provided below.
Tip 1: For the Queue implementation, if you choose to use “head” and “tail” indices to keep track of the
number of items in the queue and you choose to initialise these to 0, your implementation will need to
leave at least one empty space in the array. (If you do not leave at least one empty array position, the
“full” and “empty” conditions are indistinguishable.)
Tip 2: In Java, it may not be possible to declare an array of some template type T directly. Instead, you
may have to declare an array of Object and cast it to a T array, such as:
T a = (T) new Object[some_size];
When the implementation is correct for single words, the output will be as follows:
[+10%] Queue and Stack declared correctly.
[+10%] Queue functions appear correct.
[+10%] Stack functions appear correct.
[+20%] Stack and Queue appear to resize correctly.
[+10%] “level” is a palindrome (correct).
[+10%] “anna” is a palindrome (correct).
[+10%] “first” is a non-palindrome (correct)
[+10%] “Matter fact” is a non-palindrome (correct)
[+10%] “Landed on his hip and busted his lip” is a non-palindrome (correct)
Grade for this assignment: 100%
You are required to submit two classes for this assignment: ArrayQueue.java and ArrayStack.java. Use
GitHub to check in the two classes required to complete the implementation. On Canvas, submit the URL
for your GitHub repository.
The assignment generates a grade (“Grade for this assignment”) based on correctness of the data
structure implementations and detection of palindromes and non-palindromes. This will be the starting
point for the grade for the assignment.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx