Lab 1 Solution

This lab involves implementing linear data structures - stacks and queues.







Overview




Fill out all of the methods in the provided skeleton code. You may add additional methods, but should NOT add additional public elds to Stack or Queue. You also should not change the name of any of the classes or les.




In main, read each line, and call isPalindrome.




In isPalindrome, iterate over the characters in the line, and process with Stack and Queue.




You should think about how to use a Stack and Queue to determine if a string is a palindrome.




In the Stack and Queue classes, ll out each of the public methods. Do NOT change the arguments or return types of the public methods. You may, however, add private methods.







Input Description




The input will be a text le, for example inSample.txt below will be provided. The rst line will contain an integer N, which is the number of lines to follow. Each of the N lines contains a string of numbers not separated by spaces.




For each line, use your stack and queue to determine if the input represents a palindrome.




The input strings are made up of non-negative numbers of di erent sizes.




5




30325




1133311




613373316




44




56




Note: When using an editor, you may also manually type in input to the command window.




However, you will be tested with a le similar to inSample.txt.




























1
Output Description




For each line of the input, if the string of numbers reads the same way forward as backwards output "This is a Palindrome.", otherwise output: "Not a Palindrome." For example, using the sample input above, your program should output:







Not a Palindrome.




This is a Palindrome.




This is a Palindrome.




This is a Palindrome.




Not a Palindrome.







Testing Protocol




We will test your program in the same fashion as lab 0. We strongly suggest you test your program in the following ways:




While creating it With inSample.txt




With the provided test.sh le found in /home/users/smergend/public/cs313/lab1/test.sh on ix-dev.




With the provided testContents class for testing your Stack and Queue data structures







Grading




This assignment will be graded as follows:




Correctness 50%




Your program compiles without errors (including the submitted les NOT containing package names at the top. Delete the package name from the top of the les before you submit them): 10% Your program runs without errors: 10%




Your program produces the correct output: 30%




Implementation 50%




Your Stack class implements all of the proper methods in O(1): 20%




Your Queue class implements all of the proper methods in O(1): 20%




Your palindrome test uses a Stack and a Queue, to achieve linear running time O(n) 10%




To earn points for implementation, your code must be clear enough for us to un-derstand







Further, you may not use any data structures from the Java standard library, the C foreign function interface, or arrays







2
Extra Credit 20%




To receive points for the extra credit you must implement a queue using two stacks:




Create a new public class le called TwoStackQueue, which has two stacks as member vari-ables




The signature of this class should be the same as the Queue class. { It should have the same public methods




{ Each public method should match in argument types (argument number, etc), and return type.




Note that this is not the same as having the same methods.




In particular, you may modify the bodies of public methods, and change add or remove private methods.




{ Amortized complexity O(1) for each operation.




create an additional public class le called EC { All the same functionality as lab1.java

{ use a TwoStackQueue instead of a Queue in the isPalindrome method




Note that EC.java will have a main method, while TwoStackQueue.java will not




Testing Extra Credit




In order to test your TwoStackQueue class, simply test it in all the same ways you tested your original program.
























































































3