Q3-Q4: A data structure called a Deque is closely related to a queue. The name d

Question

Q3-Q4: A data structure called a Deque is closely related to a queue. The name deque stands for "double-ended queue." The difference between the two is that with a deque, you can insert, remove, or view from either end of the deque. Implement a deque using a doubly-linked list. Q3: Using LinearNode.java as a base, create a new class called LinearDoubleNode.java that implements a doubly-linked list node. The nodes will need both a next and previous reference. Adding the previous reference will involving adding a new member variable (prev) and two new methods (getPrev, setPrev). You will also need to make the new class self-referential by replacing uses of LinearNode with LinearDoubleNode. Q4: Create an implementation of a Deque using LinearDoubleNode (from Q3) and DequeADT (attached). Your implementation must implement all of the methods from the DequeADT interface. See Base_A06Q4.java for a starting place. Hint: What code can be reused from Q2? Hint2: Drawing diagrams of the list, and the actions of the code, may help during debugging. DequeADT: /** * QueueADT defines the interface to a queue collection. * * @author Java Foundation * @version 4.0 */ public interface QueueADT { /** * Adds one element to the rear of this queue. * @param element the element to be added to the rear of the queue */ public void enqueue(T element); /** * Removes and returns the element at the front of this queue. * @return the element at the front of the queue */ public T dequeue(); /** * Returns without removing the element at the front of this queue. * @return the first element in the queue */ public T first(); /** * Returns true if this queue contains no elements. * @return true if this queue is empty */ public boolean isEmpty(); /** * Returns the number of elements in this queue. * @return the integer representation of the size of the queue */ public int size(); /** * Returns a string representation of this queue. * @return the string representation of the queue */ public String toString(); } LINEAR NODE: /** * Represents a node in a linked list. * * @author Java Foundations * @version 4.0 */ public class LinearNode { private LinearNode next; private T element; /** * Creates an empty node. */ public LinearNode() { next = null; element = null; } /** * Creates a node storing the specified element. * @param elem element to be stored */ public LinearNode(T elem) { next = null; element = elem; } /** * Returns the node that follows this one. * @return reference to next node */ public LinearNode getNext() { return next; } /** * Sets the node that follows this one. * @param node node to follow this one */ public void setNext(LinearNode node) { next = node; } /** * Returns the element stored in this node. * @return element stored at the node */ public T getElement() { return element; } /** * Sets the element stored in this node. * @param elem element to be stored at this node */ public void setElement(T elem) { element = elem; } } HERE is the Q4 base that was given to help start the program. public class Base_A06Q4 { /** * Program entry point for deque testing. * @param args Argument list. */ public static void main(String[] args) { LinkedDeque deque = new LinkedDeque(); System.out.println("DEQUE TESTING"); /

Explanation / Answer

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<Item> implements Iterable<Item> {

private int s;
private Node f;
private Node l;

public DefDeque() {

}

public boolean isEmpty() {
return f == null;
}

public int size() {
return s;
}

public void addF(Item it) {
throwIfNull(it);

Node newF = new Node();
newFt.item = it;

if (f != null) {
newF.next = f;
f.previous = newF;
}
f = newF;
if (l == null) last = f;

s++;
}

public Item removeFirst() {
throwIfEmpty();

Node oldF = f;
f = f.next;

if (f == null)
l = null;
else
f.previous = null;

size--;

return oldF.it;
}

public void addLast(Item it) {
throwIfNull(it);

Node newL = new Node();
newL.it = it;

if (l != null) {
newL.previous = l;
l.next = newL;
}
l = newL;
if (f == null) f = l;

s++;
}

public Item removeLast() {
throwIfEmpty();

Node oldL = l;
l = oldL.previous;

if (l == null)
f = null;
else
l.next = null;

s--;

return oldL.item;
}

private void throwIfEmpty() {
if (f == null)
throw new NoSuchElementException();
}

private void throwIfNull(Item it) {
if (it == null)
throw new NullPointerException();
}

@Override
public Iterator<Item> iterator() {
return new ItemsIterator();
}

private class ItemsIterator implements Iterator<Item> {

private Node curr;

public ItemsIterator() {
curr = f;
}

@Override
public boolean hasNext() {
return curr != null;
}

@Override
public Item next() {
if (curr == null)
throw new NoSuchElementException();

Item it = curr.it;
curr = curr.next;
return it;
}

@Override
public void remove() {
throw new UnsupportedOperationException();
}
}

private class Node {
Item it;
Node next;
Node previous;
}

}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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