In this project you will create a deque that does not allow duplicates. The func
ID: 3875002 • Letter: I
Question
In this project you will create a deque that does not allow duplicates. The function of the deque’s operations addToBack and addToFront leave the deque unchanged if the the objects are already in the deque, Add two operations, moveToBack and moveToFront. These operations will move an existing object the back (or front) of the deque, if the object is present in the deque. If the object is not already in the deque, it will add the object to the back (or front) of the deque. Create an interface NoDuplicatesDequeInterface that extends DequeInterface. Then write class - named CSE274Deque - that is a doubly linked implementation of NoDuplicatesDequeInterface. Finally, write a program that adequately demonstrates your new class. public interface.
public interface DequeInterface<T> {
/**
* Adds a new entry to the front/back of this dequeue.
*
* @param newEntry An object to be added.
*/
public void addToFront(T newEntry);
public void addToBack(T newEntry);
/**
* Removes and returns the front/back entry of this dequeue.
*
* @return The object at the front/back of the dequeue.
* @throws EmptyQueueException if the dequeue is empty before the operation.
*/
public T removeFront();
public T removeBack();
/**
* Retrieves the front/back entry of this dequeue.
*
* @return The object at the front/back of the dequeue.
* @throws EmptyQueueException if the dequeue is empty before the operation.
*/
public T getFront();
public T getBack();
/*
* Detects whether this dequeue is empty.
*
* @return True if the queue is empty, or false otherwise.
*/
public boolean isEmpty();
/* Removes all entries from this dequeue. */
public void clear();
public int size();
} // end DequeInterface
public class CSE274Deque implements NoDuplicatesDequeInterface {
@Override
public void addToFront(Object newEntry) {
// TODO Auto-generated method stub
}
@Override
public void addToBack(Object newEntry) {
// TODO Auto-generated method stub
}
@Override
public Object removeFront() {
// TODO Auto-generated method stub
return null;
}
@Override
public Object removeBack() {
// TODO Auto-generated method stub
return null;
}
@Override
public Object getFront() {
// TODO Auto-generated method stub
return null;
}
@Override
public Object getBack() {
// TODO Auto-generated method stub
return null;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
@Override
public void clear() {
// TODO Auto-generated method stub
}
@Override
public int size() {
// TODO Auto-generated method stub
return 0;
}
@Override
public void moveToBack() {
// TODO Auto-generated method stub
}
@Override
public void moveToFront() {
// TODO Auto-generated method stub
}
}
Explanation / Answer
public class CSE274Deque implements DequeInterface {
class Node {
Object data;
Node next, prev;
public Node(Object data, Node next, Node prev) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
private Node head, tail;
private int size;
public CSE274Deque() {
size = 0;
head = tail = null;
}
@Override
public void addToFront(Object newEntry) {
Node tmp = head;
while (tmp != null) {
if (Objects.equals(tmp.data, newEntry))
return;
tmp = tmp.next;
}
tmp = new Node(newEntry, head, null);
if (head != null)
head.prev = tmp;
else
tail = tmp;
head = tmp;
size ++;
}
@Override
public void addToBack(Object newEntry) {
Node tmp = head;
while (tmp != null) {
if (Objects.equals(tmp.data, newEntry))
return;
tmp = tmp.next;
}
tmp = new Node(newEntry, null, tail);
if (tail != null)
tail.next = tmp;
else
head = tmp;
tail = tmp;
size ++;
}
@Override
public Object removeFront() {
if (head == null)
return null;
Node tmp = head;
head = head.next;
if (head == null)
tail = null;
else
head.prev = null;
size --;
return tmp.data;
}
@Override
public Object removeBack() {
if (isEmpty())
return null;
Node tmp = tail;
tail = tail.prev;
if (tail == null)
head = null;
else
tail.next = null;
size --;
return tmp.data;
}
@Override
public Object getFront() {
return head;
}
@Override
public Object getBack() {
return tail;
}
@Override
public boolean isEmpty() {
return head == null;
}
@Override
public void clear() {
head = tail = null;
}
@Override
public int size() {
return size;
}
@Override
public void moveToBack() {
// TODO Auto-generated method stub
}
@Override
public void moveToFront() {
// TODO Auto-generated method stub
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.