Implement two versions of a generic queue: One using an array and another using
ID: 3663679 • Letter: I
Question
Implement two versions of a generic queue: One using an array and another using a singly linked list. Remember queues are first in first out (FIFO). Use the driver to then test each of the queues. Create a class GenArrayQueue which has the following: Instance Variables queue which an array of the generic type T Class Variables (IE constant) DEFAULT_SIZE this integer value takes the value of 100 Constructors A default constructor that initializes queue of the default size A parameterized constructor which takes in a whole number that sets the size of the array Methods enqueue - This method returns no value and takes a variable of type T and adds it to the last available spot in the array. dequeue - This method removes and returns the first element in the queue peek - This method returns the first element of the queue without removing it showQueue - Prints out the queue in order Create another class GenLLQueue which has the following: Internal class ListNode whichExplanation / Answer
// GenericArrayQueue.java
public class GenericArrayQueue<Item> {
private final int DEFAULT_SIZE = 100;
private Item[] q; // queue elements
private int N ; // number of elements on queue
private int first; // index of first element of queue
private int last; // index of next available slot
/**
* Initializes an empty queue.
*/
public GenericArrayQueue() {
q = (Item[]) new Object[DEFAULT_SIZE];
first = 0;
last = 0;
N = 0;
}
public boolean isEmpty() {
return N == 0;
}
/**
* Returns the number of items in this queue.
* @return the number of items in this queue
*/
public int size() {
return N;
}
/**
* Adds the item to this queue.
* @param item the item to add
*/
public void enqueue(Item item) {
if (N == q.length) {// queue is full
}
q[last++] = item; // add item
if (last == q.length) last = 0; // wrap-around
N++;
}
public Item dequeue() {
if (isEmpty())
System.out.println("Queue underflow");
Item item = q[first];
q[first] = null; // to avoid loitering
N--;
first++;
if (first == q.length) first = 0; // wrap-around
return item;
}
public Item peek() {
if (isEmpty()){
System.out.println("Queue underflow");
}
return q[first];
}
public void showQueue(){
for(int i = 0; i<=N; i++) {
System.out.println(dequeue());
}
}
public static void main(String[] args) {
GenericArrayQueue<String> q = new GenericArrayQueue<String>();
}
}
//GenLLQueue.java
public class GenLLQueue<Item> {
private int N; // number of elements on queue
private Node first; // beginning of queue
private Node last; // end of queue
// helper linked list class
private class Node {
private Item item;
private Node next;
}
/**
* Initializes an empty queue.
*/
public GenLLQueue() {
first = null;
last = null;
N = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
public Item peek() {
if (isEmpty())
System.out.println("Queue underflow");
return first.item;
}
public void enqueue(Item item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
N++;
}
public Item dequeue() {
if (isEmpty())
System.out.println("Queue underflow");
Item item = first.item;
first = first.next;
N--;
if (isEmpty()) last = null; // to avoid loitering
return item;
}
public void showQueue() {
Node start = first;
while(first != null) {
System.out.println(dequeue().toString());
}
}
}