Lab 5: Queue from 2 Stacks (100 pts)
Due Tuesday, February 13 at 9:20am on Canvas

Pair 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)