In the file Queue.java (provided with this homework), a Queue class is defined w

Question

In the file Queue.java (provided with this homework), a Queue class is defined which allows regular queue operations, and the queue is implemented based on an int array. Here we only use one pointer next, instead of two as mentioned in the lecture (in other words, in this question front is always 0). In this problem you need to (1) Complete the two methods: enqueue and dequeue. Hint: (1) when enqueuing, you need to do resizing if the current array is full, and the resize() method is already given; (2) when dequeuing, after you remove A[0] from the array, you need to move everything over, i.e., move A[i] to A[i 1], and adjust next. (2) Design your own tests (at least 10 tests) in the main method to show the correctness of your code. You can take a look at how tests are designed in the first question to get an idea. Note: Two methods, printArray and toString, are also provided to help you debug your code.

Following is the code of queue.java:

public class Queue {

private int[] A = new int[10];
private int next = 0;

public void enqueue(int k) {
// your code here
// just put the new element at the end
}

public int dequeue() {
// your code here
// save A[0] in a temporary variable, then move everything over, and reset next
return 0; // your code here
}

public int size() {
return next;
}

public boolean isEmpty() {
return (next == 0);
}

public boolean isFull() {
return (next == A.length);
}

private void resize() {
int[] B = new int[A.length * 2];
for(int i = 0; i < A.length; ++i)
B[i] = A[i];
A = B;
}

public String toString() {
  
String s = "[";
if(isEmpty()) {
return s + "]";
}
else {
for(int i = next-1; i > 0; --i) {
s += (A[i] + ",");
}
s += A[0] + "]";
return s;
}
}

// debugging routine
private void printArray() {
System.out.print("[");
if(isEmpty()) {
System.out.println("]");
return;
}
else {
for(int i = 0; i < A.length-1; ++i) {
System.out.print(A[i] + ",");
}
System.out.println(A[A.length-1] + "] next = " + next);
}
}

// Unit Test
public static void main(String[] args) {

  
}
}

Explanation / Answer

public void enqueue(int k) {
        A[tail] = k;
        tail = (tail + 1) % array.length;
        size++;
    }

    public void dequeue() {
        if (size == 0) {
            throw new NoSuchElementException("Cannot remove from empty queue");
        }
        A item = A[head];
        array[head] = null;
        head = (head + 1) % array.length;
        size--;
        return item;
    }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.