PLATFORM INDEPENDENCE

• Please see Syllabus for more information.
• Your solution has to be platform-independent; it must run on any platforms including any online IDEs:
  • You solution should be free of any use of packages. Example, absolutely no

  • /* Java Program Example - Java Import Packages *
    package YOUR_CUSTOM_PACKAGE HERE;

  • Your solution, regardless of how many classes it has, should be in one .java file.
  • Your solution has to run on any online IDEs.
  • If your solution fails the platform-independence criteria, you will have to resubmit work subject to the late penalty.
  • The Late Work policy applies for all late submissions.
  • Your solution should be reusable, meaning it will be invoked and validated against a series of input sequentially to produce consistent outcomes like so:

  Solution sol = new Solution();
  sol.your_method1(test_input_1...);
  sol.your_method2(test_input_2 ...);
  

PROBLEM 1

( 10 points ) You learn in class as well as in reading about the Array-Based Queue Implementations, specifically the “Floating Front Design” to implement a queue using a fixed-size array. The following two scenarios from your lecture slides illustrate how this design works:

Scenario #1

Scenario #2

You are responsible for implementing the areas of code indicated with YOUR CODE HERE. This Solution class implements a constructor that builds an array of a dynamic capacity at construction time. In this problem, you will be following the above mentioned Floating Front design in your textbook and lecture, and implement the FOUR (4) solution methods: add()/remove()/peek()/isEmpty(). Note these methods are named differently and both the front and rear pointers have different initialized values in this problem than what is in the lecture. DO NOT ALTER THEM in your code:

public class HW6_1 {
   public static void main(String[] args) {
      // your solution method will be tested as such, with random sequential input
      // TEST CASE #1: instantiate a queue of capacity = 1
      Solution sol = new Solution(1);
      sol.getFront(); // -1
      sol.getRear(); // -1
      sol.add(8);
      sol.getFront(); // 0
      sol.getRear(); // 0
      sol.peek(); // 8
      sol.remove(); // 8
      sol.isEmpty(); // true
      sol.getFront(); // -1, when queue is empty
      sol.getRear(); // -1, when queue is empty

      // TEST CASE #2: instantiate a queue of capacity = 3
      Solution sol = new Solution(3);
      sol.add(1);
      sol.add(2);
      sol.add(3);
      sol.getFront(); // 0
      sol.getRear(); // 2
      sol.remove(); // 1
      sol.getFront(); // 1
      sol.getRear(); // 2
      // etc
   }
}

class Solution {
   // Dynamic array size
   private int capacity;
   // Queue
   private int[] elements;
   // Dynamic queue size
   private int numElements = 0;
   // Dynamic index for the front of queue, defaulting to -1 when the queue is empty
   private int front = -1;
   // Dynamic index for the rear of queue, defaulting to -1 when the queue is empty
   private int rear = -1;

   // Constructor
   public Solution(int capacity) {
      this.capacity = capacity;
      this.elements = new int[this.capacity];
   }
   // Get the front index
   public int getFront() {
      return this.front;
   }
   // Get the rear index
   public int getRear() {
      return this.rear;
   }

   /* =====================================
   /* !!! DO NOT MODIFY ABOVE THIS LINE!!!
   /* ====================================
  /**
   * PURPOSE: 
   * PARAMETERS: 
   * RETURN VALUES:
  */
  public void add(int x) { 
     // YOUR CODE HERE
  }

  /**
   * PURPOSE: 
   * PARAMETERS: 
   * RETURN VALUES:
  */
  public int remove() { 
     // YOUR CODE HERE
  }

  /**
   * PURPOSE: 
   * PARAMETERS: 
   * RETURN VALUES:
  */
  public int peek() { 
     // YOUR CODE HERE
  }
  
  /**
   * PURPOSE: 
   * PARAMETERS: 
   * RETURN VALUES:
  */
  public boolean isEmpty() { 
    // YOUR CODE HERE
  }
}

CONSTRAINTS / ASSUMPTIONS

• This problem tests your understanding of how queue works in Java by implementing it from scratch using a fixed-size array.
• All operations called on the queue are valid. In other words, both remove() and peek() will NOT be called on an empty queue, and add() won’t be called on a queue at capacity prompting to resize. This means you won’t have to create any Exceptions to handle errors.
• NOTE: when the queue is empty, both front and rear should have an index of -1.
• Your solution will be tested against 9-10 test cases; -1 for each failed test.
• Each test case includes a combination of queue operations, and getFront() and getRear() to test the correctness of your “Floating Front Design”.

SUBMISSION

• Submit your solution in HW6_1.java.
• There are two classes in this Java code. One of them is your HW6_1 class, and the other is the same top-level class (the one without the public access modifier) named Solution.