Lab 5: Queue from 2 Stacks (100 pts)
Due Monday, October 29 at 11:59pm on Canvas


Pair Programming Extra Credit Opportunity (5 pts)

  • Both partners fill in, sign and date the pair programming contract (Both partners).
  • 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.


Queue.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.

/**
 * Queue.java
 * @author
 * @author
 * CIS 22C Lab 5
 */
public class Queue {
    private Stack<String> s1;
    private Stack<String> s2;
    
    /**Constructors**/
    
    /**
     * Default constructor for the
     * Queue class
     */
    public Queue() {
        
    }
    
    /**
     * Copy constructor for the
     * Queue class
     * @param q the original Queue
     * to copy
     */
    public Queue(Queue q) {
        
    }
    
    /**Mutators**/
    
    /**
     * Inserts new data to the end
     * of the Queue
     * @param data the value to insert
     */
    public void enqueue(String data) {
        
    }
    
    /**
     * Removes data from the front of
     * the Queue
     */
    public void dequeue() {
        
    }
    
    /**
     * 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 q) {
        
    }
    
    /**Accessors**/
    
    /**
     * Returns the value stored
     * at the front of the Queue
     * @return
     */
    public String getFront() {
        return "";
    }
    
    /**
     * 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, each separated by a
     * comma, and ending with a new line
     * character
     */
    @Override public String toString() {
        return "";
    }
}


Queue.java File

  • Additionally, below is an **incomplete** QueueTest.java file.
  • Copy and paste the below code into a file called QueueTest.java.
  • 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
/**
 * QueueTest.java
 * @author
 * @author
 * CIS 22C Lab 5
 */
public class QueueTest {
    public static void main(String[] args) {
        Queue q = new Queue();
        System.out.println("**Testing enqueue()**");
        q.enqueue("1");
        System.out.println("Should print 1: " + q);
        q.enqueue("2");
        System.out.println("Should print 1 2: " + q);
        q.enqueue("3");
        System.out.println("Should print 1 2 3: " + q);
       
        System.out.println("\n**Testing dequeue()**");
        q.dequeue();
        System.out.println("Should print 2 3: " + q);
       
        System.out.println("\n**Testing isEmpty()**");
        Queue 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()**");
        q2.enqueue("A");
        q2.enqueue("B");
        q2.enqueue("C");
        q2.enqueue("D");
        q.append(q2);
        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));
        q.dequeue();
        q.dequeue();
        System.out.println("Should print true: " + q.equals(q2));
        q.dequeue();
       
        System.out.println("\n**Testing Copy Constructor**");
        Queue q3 = new Queue(q2);
        System.out.println("Should print A B C D: " + q3);
        q3.enqueue("E");
        q3.enqueue("F");
       
        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 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
  • Optional: Submit your pair programming contract if you completed the assignment as a pair program.
  • Please do not submit your files in a zipped folder or other compressed type or you will lose 5 points.

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)