CS 206 - Introduction to Data Structures
Assignment 5: Due 11:59AM Tuesday October 22
You are not allowed to change any of the imported code: ArrayStack.java, StackInterface.java, QueueInterface.java, and Deque.java.
Part 1
Copy ArrayStack.java and StackInterface.java and QueueInterface.java from /home/gtowell/Public206/data/a5 into an eclipse project using the method described in the recent labs. Write a class called TwoStacksQueue that implements QueueInterface interface as follows:
- Your class will store two ArrayStack objects as instance variables.
- There should not be any other array/ArrayList/linked list used within your implementation
- Override toString for TwoStacksQueue to return a String that contains the contents of the current Queue in the following format (elment1, element2, ..., elementN)
A TwoStacksQueue object is a Queue and should behave as a Queue (FIFO). Since you are using two stacks to simulate a Queue, it will certainly not be the most efficient implmentation of a Queue and that’s ok - just as long as you know that and can analyze the run-time appropriately in the README. Your README should contain a section labaled "Discussion" that contains a discussion on the design of your data structure, in particular how you implemented enqueue and dequeue operations. In addition, you should provide a worst-case big-O analysis of each of these operations.
Part 2
Implement DeQueue (double-ended queue where we can insert and delete at both ends) with an array used in a circular fashion. Copy DequeInterface.java from /home/gtowell/Public206/a5, which specifies the the Dequeue interface that you must implement. Override toString for ArrayDeque to return a String that contains the contents of the current DeQueue in the following format (element1, element2, ..., elementN).
Part 3
Write a driver program Main.java that tests all the methods you have implemented in your TwoStacksQueue and Dequeue implementations. You should include enough tests to clearly demonstrate that your implementation works. For instance, the code in the Queue implementation (https://cs.brynmawr.edu/Courses/cs206/fall2019/lec10/ArrayQueue.java.txt) from class on October 3 is a pretty good start.
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)
- The writeup as described above. This should be within the README, but it is acceptable as a separate 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 are using Eclipse, and that you created a project named AssignmentN in the directory /home/YOU/cs206/
- For this assignment N=5
- Put the README file into the project directory (/home/YOU/cs206/AssignmentN)
- Put your writeup in this same directory.
- Go to the directory /home/YOU/cs206
- Enter submit -c 206 -p N -d AssignmentN
For more on using the submit script click here