Lab 5: Queue from 2 Stacks (100 pts)
Due Monday, February 10 at 11:59pm 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
  • Test your methods inside a test file named
  • 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 and, respectively.
  • Name your JUnit test files as follows:,,,,,,,
  • Additionally, add your class from Lab 3 to your project folder, as your must run with your Stack class from Lab 3.
    • You may create a new file inside of your Lab 5 project folder and copy and paste the contents of 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 from the feedback provided by the professor for Lab 3, please make these changes for this Lab.
    • The instructor will again be reviewing your class for this lab and will deduct points for any methods that are not correctly implemented.
    • Please get help if you are uncertain. File

  • Copy and paste the below code into a file named
  • 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.

 * @author
 * @author
 * CIS 22C Lab 5
public class Queue<T> {
    private Stack<T> s1;
    private Stack<T> s2;
     * Default constructor for the
     * Queue class
    public Queue() {
     * Copy constructor for the
     * Queue class
     * @param q the original Queue
     * to copy
    public Queue(Queue<T> q) {
     * Inserts new data to the end
     * of the Queue
     * @param data the value to insert
    public void enqueue(T data) {
     * Removes data from the front
     * @precondition length != 0
    public void dequeue() throws NoSuchElementException{
     * Appends the values of a
     * a new Queue onto the end
     * of this Queue
     * @param q the Queue whose
     * values to append
    public void append(Queue<T> q) {
     * Returns the data at the front
     * @precondition length != 0
     * @return the front of the Queu
    public T getFront() throws NoSuchElementException{
        return null;
     * Returns the current size of
     * this Queue
     * @return the current size
    public int getSize() {
        return 0;
     * Returns whether this Queue is
     * currently empty
     * @return whether the Queue is empty
    public boolean isEmpty() {
        return false;
     * Determines whether two Queues
     * have the data stored in the same
     * order
    @Override public boolean equals(Object o) {
        return false;
    /**Additional Operations**/
     * Creates a String to store the values
     * the Queue,separated with spaces and
ending with a new line character
    @Override public String toString() {
        return "";
} File

  • Additionally, below is an **incomplete** file.
  • Copy and paste the below code into a file called
  • Add two additional method calls per method, including:
    • Test all preconditions - do the messages that print out display the word Queue or Stack? Hint: this is a Queue class, so the error message should state Queue
    • Please use try-catch when testing code where an exception is thrown
 * @author
 * @author
 * CIS 22C Lab 5
public class QueueTest {
    public static void main(String[] args) {
        Queue<String> q = new Queue<>();
        System.out.println("**Testing enqueue()**");
        System.out.println("Should print 1: " + q);
        System.out.println("Should print 1 2: " + q);
        System.out.println("Should print 1 2 3: " + q);
        System.out.println("\n**Testing dequeue()**");
        System.out.println("Should print 2 3: " + q);
        System.out.println("\n**Testing isEmpty()**");
        Queue<String> q2 = new Queue<>();
        System.out.println("Should print true: " + q2.isEmpty());
        System.out.println("Should print false: " + q.isEmpty());
        System.out.println("\n**Testing append()**");
        System.out.println("Should print 2 3 A B C D: " + q);
        System.out.println("\n**Testing getFront()**");
        System.out.println("Should print A: " + q2.getFront());
        System.out.println("\n**Testing getSize()**");
        System.out.println("Should print 6: " + q.getSize());
        System.out.println("\n**Testing Equals**");
        System.out.println("Should print true: " + q2.equals(q2));
        System.out.println("Should print false: " + q.equals(q2));
        System.out.println("Should print true: " + q.equals(q2));
        System.out.println("\n**Testing Copy Constructor**");
        Queue<String> q3 = new Queue<String>(q2);
        System.out.println("Should print A B C D: " + q3);
        System.out.println("Testing for Deep Copy:");
        System.out.print("Should print A B C D E F: " + q3);
        System.out.print("Should print A B C D: " + q2);

What to Submit

  • Submit your, and 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
    • 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 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)