This is java. Deque. A double-ended queue or deque (pronounced \"deck\") is a ge
ID: 3593252 • Letter: T
Question
This is java.
Deque. A double-ended queue or deque (pronounced "deck") is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure. Create a generic data type Deque, based on the LinkedQueue.java code from the previous lab, that implements the following API:
Corner cases. Throw a java.lang.NullPointerException if the client attempts to add a null item; throw a java.util.NoSuchElementException if the client attempts to remove an item from an empty deque; throw a java.lang.UnsupportedOperationException if the client calls the remove() method in the iterator; throw a java.util.NoSuchElementException if the client calls the next() method in the iterator and there are no more items to return.
Performance requirements. Your deque implementation must support each deque operation (including construction) in constant worst-case time and use space linear in the number of items currently in the deque. It is possible to implement such a deque with a circular array (beyond the scope of this class), but here, we'll do it with a doubly-linked list (in which each node has a "next" and "prev" link). If you completed your Deque implementation in the previous lab, you may reuse it here.
Your Deque implementation should include an iterator that supports each operation (including construction) in constant worst-case time. Your main function should include code that tests this with a sequence of add and remove actions.
Explanation / Answer
Given below is the code for deque with output. Please don't forget to rate the answer if it helped. Thank you.
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class Deque<Item> implements Iterable<Item> {
class DNode
{
Item data;
DNode prev;
DNode next;
DNode(Item t)
{
this(t, null, null);
}
DNode(Item t, DNode pr, DNode nx)
{
data = t;
prev = pr;
next = nx;
}
}
private DNode head, tail;
private int size;
public Deque() // construct an empty deque
{
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() // is the deque empty?
{
return size == 0;
}
public int size() // return the number of items on the deque
{
return size;
}
public void addFirst(Item item) // add the item to the front
{
if(item == null)
throw new NullPointerException("null not allowed");
DNode n = new DNode(item, null, head);
if(head != null)
head.prev = n;
head = n;
if(tail == null)
tail = n;
size++;
}
public void addLast(Item item) // add the item to the end
{
if(item == null)
throw new NullPointerException("null not allowed");
DNode n = new DNode(item, tail, null);
if(tail != null)
tail.next = n;
tail = n;
if(head == null)
head = n;
size++;
}
public Item removeFirst() // remove and return the item from the front
{
if(isEmpty())
throw new NoSuchElementException("deque is empty");
Item val = head.data;
head = head.next;
size --;
if(head != null)
{
head.prev = null;
}
else //now queue is empty
tail = null;
return val;
}
public Item removeLast() // remove and return the item from the end
{
if(isEmpty())
throw new NoSuchElementException("deque is empty");
Item val = tail.data;
tail = tail.prev;
size --;
if(tail != null)
tail.next = null;
else //now queue is empty
head = null;
return val;
}
public Iterator<Item> iterator() // return an iterator over items in order from front to end
{
return new DequeIterator();
}
class DequeIterator implements Iterator<Item>
{
DNode current;
public DequeIterator() {
current = head;
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
if(!hasNext())
throw new NoSuchElementException("deque is empty");
Item val = current.data;
current = current.next;
return val;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
public String toString()
{
String str = "";
DNode n = head;
while(n != null)
{
str += n.data.toString() + " ";
n = n.next;
}
str += " ";
return str;
}
public static void main(String[] args) // unit testing (required)
{
Deque<Integer> deq = new Deque<>();
System.out.println("Adding 1 2 3 using addFirst()");
deq.addFirst(1);
deq.addFirst(2);
deq.addFirst(3);
System.out.println("Using iterator... ");
Iterator<Integer> it = deq.iterator();
while(it.hasNext())
System.out.print(it.next()+ " " );
System.out.println();
System.out.println("Adding 4 5 6 using addLast()");
deq.addLast(4);
deq.addLast(5);
deq.addLast(6);
System.out.println(deq);
System.out.println("removed " + deq.removeFirst() + " using removeFirst()");
System.out.println("removed " + deq.removeFirst() + " using removeFirst()");
while(!deq.isEmpty())
System.out.println("removed " + deq.removeLast() + " using removeLast()");
}
}
output
Adding 1 2 3 using addFirst()
Using iterator...
3 2 1
Adding 4 5 6 using addLast()
3 2 1 4 5 6
removed 3 using removeFirst()
removed 2 using removeFirst()
removed 6 using removeLast()
removed 5 using removeLast()
removed 4 using removeLast()
removed 1 using removeLast()
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.