JAVA data structures

1. Complete the implementations of the a. ArrayQueue dequeue isEmpty b. ArrayUnbndQueue dequeue isEmpty c. LinkedQueue 2. Include a toString method for each of the Queue implementations 3. Include a size() method for each of the Queue implementations. This method should return the number of elements in the queue (not the maximum capacity) 4. Update the queue tester to include tests for all three queues, including a. isEmpty method true and false b. isFull method empty and false (for the ArrayQueue) c. enqueue with exception for ArrayQueue d. dequeue - with/without exception for all e. toString - at various points before/after queue and dequeue

LinkedQueue Java Class

package ch05.queues;

import support.LLNode;

public class LinkedQueue implements UnboundedQueueInterface {

LLNode front;

LLNode rear;

int numElements;

public LinkedQueue() {

numElements = 0;

}

@Override

public T dequeue() throws QueueUnderflowException {

// TODO Auto-generated method stub

T data;

if (isEmpty())

throw new QueueUnderflowException("Queue is empty");

data = front.getInfo();

front = front.getLink();

if (front == null) {

rear = null;

}

numElements--;

return data;

}

@Override

public boolean isEmpty() {

// TODO Auto-generated method stub

return (front == null);

}

@Override

public void enqueue(T element) {

// TODO Auto-generated method stub

LLNode newNode = new LLNode(element);

if (isEmpty()) {

front = newNode;

}

else {

rear.setLink(newNode);

}

rear = newNode;

numElements++;

}

}

ArrayUnbndQueue Java Class

package ch05.queues;

public class ArrayUnbndQueue implements UnboundedQueueInterface {

protected T[] queue;

protected int front;

protected int rear;

protected int numElements = 0;

protected final int DEFCAP = 5;

public ArrayUnbndQueue() {

queue = (T[]) new Object[DEFCAP];

rear = DEFCAP - 1;

}

@Override

public T dequeue() throws QueueUnderflowException {

// TODO Auto-generated method stub

return null;

}

@Override

public boolean isEmpty() {

// TODO Auto-generated method stub

return false;

}

@Override

public void enqueue(T element) {

// TODO Auto-generated method stub

// TODO Auto-generated method stub

if (numElements == queue.length) {

enlarge();

}

rear = (rear + 1) % queue.length;

queue[rear] = element;

numElements++;

}

private void enlarge() {

System.out.println("increased size");

T[] newQ = (T[]) new Object[queue.length + DEFCAP];

int start = front;

for (int i = 0; i < queue.length; i++) {

newQ[i] = queue[start];

start = (start + 1) % queue.length;

}

queue = newQ;

front = 0;

rear = numElements-1;

}

}

ArrayQueue Java

package ch05.queues;

public class ArrayQueue implements BoundedQueueInterface {

protected T[] queue;

protected int front;

protected int rear;

protected int numElements = 0;

protected final int DEFCAP = 100;

public ArrayQueue() {

queue = (T[]) new Object[DEFCAP];

rear = DEFCAP - 1;

}

public ArrayQueue(int capacity) {

queue = (T[]) new Object[capacity];

rear = capacity - 1;

}

@Override

public T dequeue() throws QueueUnderflowException {

// TODO Auto-generated method stub

return null;

}

@Override

public boolean isEmpty() {

// TODO Auto-generated method stub

return false;

}

@Override

public void enqueue(T element) throws QueueOverflowException {

// TODO Auto-generated method stub

if (isFull()) {

throw new QueueOverflowException("Queue is full");

}

rear = (rear + 1) % queue.length;

queue[rear] = element;

numElements++;

}

@Override

public boolean isFull() {

// TODO Auto-generated method stub

return (numElements == queue.length);

}

}

QueueTester Java Class

package ch05;

import ch05.queues.*;

public class QueueTester {

public static void main(String[] args) throws QueueUnderflowException {

// TODO Auto-generated method stub

LinkedQueue lQ = new LinkedQueue();

lQ.enqueue("a");

lQ.enqueue("b");

System.out.printf("dequeue %s ", lQ.dequeue());

System.out.printf("dequeue %s ", lQ.dequeue());

System.out.printf("dequeue %s ", lQ.dequeue());

}

}