Lab 5: Queue from 2 Stacks (100 pts)
Due Tuesday, February 13 at 9:20am on CanvasPair Programming Required or No Credit!
- Both partners fill in, sign and date the pair programming contract and BOTH partners submit.
- Only ONE partner submits the lab assignment on Canvas. Please make sure both your names are on ALL the files.
Assignment Specifications
- Here is a common interview question: implement a queue using two stacks.
- We
will create an implementation of this interview question for Lab 5, and
you will then be ready if you are asked this question on your next
interview!
- Given
the below header file (must remain unchanged), write the Queue methods
whose signatures are provided in a file named Queue.java.
- Test your methods inside a test file named QueueTest.java
- Additionally, implement JUnit test classes (3 assertEquals() calls per class) for the below methods:
- enqueue
- dequeue
- getFront
- getSize
- isEmpty
- append
- equals
- copy constructor
- Name your source files Queue.java and QueueTest.java, respectively.
- Name your JUnit test files as follows: EnqueueTest.java, DequeueTest.java, GetFrontTest.java, GetSizeTest.java, IsEmptyTest.java, AppendTest.java, EqualsTest.java, CopyTest.java
- Additionally,
add your Stack.java class from Lab 3 to your project folder, as your
Queue.java must run with your Stack class from Lab 3.
- You
may create a new Stack.java file inside of your Lab 5 project folder
and copy and paste the contents of Stack.java from Lab 3 into this new
file.
- Or you may import this file in another way.
- Note:
If any changes need to be made to Stack.java from the feedback provided
by the professor for Lab 3, please make these changes for this Lab.
- The
instructor will again be reviewing your Stack.java class for this lab
and will deduct points for any methods that are not correctly
implemented.
- Please get help if you are uncertain.
Stack.java File
- Copy and paste the below code into a file named Queue.java.
- You are not permitted to alter anything about this class or its methods or add any additional member variables or methods.
- You should only implement the methods whose signatures are provided.
#ifndef STACK_H_ #define STACK_H_
#include <iostream> #include <string> #include "Queue.h" using namespace std;
class Stack { public: /**manipulation procedures*/
void pop(); //removes an element from the top of the stack //precondition: the stack isn't empty //postcondition: an element has been removed from the top of the stack
void push(string data); //adds an element to the top of the stack //postcondition: an element added to the top of the stack
/**accessors*/
string getTop(); //returns the element at the top of the stack //precondition: the stack is not empty
int getSize(); //returns the size of the stack
bool isEmpty(); //returns whether the stack is empty
/**additional queue operations*/ void print(); //prints the elements in the stack to stdout
private: Queue<string> q1; Queue<string> q2;
};
#endif /* STACK_H_ */
What to Submit - Submit your Stack.java, Queue.java and QueueTest.java files to Canvas when you are finished.
- Additionally, submit your JUnit test files as specified in the directions above to Canvas when you are finished
- Submit your pair programming contract (both partners)
- Please submit each file separately (no zip files or other compressed file type -5 pts).
- Please remove all package statements before submitting (-5 pts).
How You Will Be Graded:
- 6.5 points for each correctly implemented method in Queue.java
- Note that all methods should run in a maximum of O(n) time. Any method that has a larger Big-O runtime will lose 2 points.
- 3
points for each JUnit test file as specified above (1 point per correct
assertEquals that tests the method you are trying to test)
- 11
points for a QueueTest.java file in which each method is tested
(called) at least twice more than the method calls that are provided,
including code to test for violation of preconditions.
- No
credit if your code does not compile or runs with an error message or I
am unable to run your code (e.g. you did not submit one of your files
or you named one of your files incorrectly)
|
|