Use this code: D. 12 points -- Use a circular doubly linked chain to implement t
ID: 3600834 • Letter: U
Question
Use this code:
D. 12 points -- Use a circular doubly linked chain to implement the ADT deque. In a doubly linked chain, the first and last nodes each contain one null reference, since the first node has no previous node and the last node has no node after it. In a circular doubly linked chain, the first node references the last node, and the last node references the first. Only one external reference is necessary-a reference to the first node-since you can quickly get to the last node from the first node. The code for this problem is provided in the Assignment-03-Code.zip archive. Your output must be identical to the output to the right.Explanation / Answer
package chegg;
import java.util.Arrays;
public class CircularDoublyLinkedDeque<T> {
private T[] circularQueue;
private int sizeQueue;
private DLNode firstNode;
@SuppressWarnings("unchecked")
public CircularDoublyLinkedDeque(int capacity, String[] elements) {
sizeQueue = capacity;
T[] tempQueue = (T[]) new Object[capacity];
for (int i = 0; i < capacity; i++) {
tempQueue[i] = (T) elements[i];
}
circularQueue = tempQueue;
}
public void addToBack(T newEntry) {
try {
for (int i = 0; i < circularQueue.length; i++) {
if (circularQueue[i] == null) {
circularQueue[i] = newEntry;
break;
}
}
sizeQueue++;
} catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
}
public void addToFront(T newEntry) {
try {
for (int i = (circularQueue.length - 1); i == 0; i--) {
circularQueue[i + 1] = circularQueue[i];
}
circularQueue[0] = newEntry;
sizeQueue++;
} catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
}
@SuppressWarnings("unchecked")
public T removeFront() {
if (isEmpty()) {
return null;
}
T result = circularQueue[0];
circularQueue[0] = null;
for (int i = 1; i < circularQueue.length; i++) {
circularQueue[i - 1] = circularQueue[i];
}
sizeQueue--;
T[] tempQueue = (T[]) new Object[sizeQueue];
for (int i = (sizeQueue - 1); i >= 0; i--) {
tempQueue[i] = circularQueue[i];
}
circularQueue = tempQueue;
return result;
}
@SuppressWarnings("unchecked")
public T removeBack() {
T result = circularQueue[circularQueue.length - 1];
circularQueue[circularQueue.length - 1] = null;
sizeQueue--;
T[] tempQueue = (T[]) new Object[sizeQueue];
for (int i = (sizeQueue - 1); i >= 0; i--) {
tempQueue[i] = circularQueue[i];
}
circularQueue = tempQueue;
return result;
}
public T getFront() {
return circularQueue[0];
}
public T getBack() {
return circularQueue[circularQueue.length - 1];
}
public boolean isEmpty() {
for (int i = 0; i < circularQueue.length; i++) {
if (circularQueue[i] != null) {
return false;
}
}
return true;
}
@SuppressWarnings("unchecked")
public void clear() {
T[] tempQueue = (T[]) new Object[0];
circularQueue = tempQueue;
}
public static void main(String srgs[]) {
String[] array = { "Joe", "Jess", "Jim", "Jill", "Jane", "Jerry" };
CircularDoublyLinkedDeque<String> doublyLinkedDeque = new CircularDoublyLinkedDeque<>(6, array);
System.out.println(doublyLinkedDeque.getFront() + " is at the front of the dequeue ");
System.out.println(doublyLinkedDeque.getBack() + " is at the back of the dequeue ");
System.out.println(doublyLinkedDeque.removeFront() + " is removed from the front of the dequeue ");
System.out.println(doublyLinkedDeque.removeBack() + " is removed from the back of the dequeue ");
System.out.println(doublyLinkedDeque.getFront() + " is at the front of the dequeue ");
System.out.println(doublyLinkedDeque.getBack() + " is at the back of the dequeue ");
doublyLinkedDeque.clear();
System.out.println("isEmpty() returns " + doublyLinkedDeque.isEmpty());
if (doublyLinkedDeque.removeFront() == null) {
System.out.println("removeFront correctly finds deque empty");
}
}
public String toString() {
return "Queue [a=" + Arrays.toString(circularQueue) + ", size =" + sizeQueue + "]";
}
private class DLNode {
private T data;
private DLNode next;
private DLNode previous;
private DLNode() {
this(null, null, null);
}
private DLNode(T dataPortion) {
this(null, dataPortion, null);
}
private DLNode(DLNode previousNode, T dataPortion, DLNode nextNode) {
data = dataPortion;
next = nextNode;
previous = previousNode;
}
private T getData() {
return data;
}
private void setData(T newData) {
data = newData;
}
private DLNode getNextNode() {
return next;
}
private void setNextNode(DLNode nextNode) {
next = nextNode;
}
private DLNode getPreviousNode() {
return previous;
}
private void setPreviousNode(DLNode previousNode) {
previous = previousNode;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.