import java.util.Iterator; // 1.3.33 Doubly linked version public class MyDeque<

Question

import java.util.Iterator;

// 1.3.33 Doubly linked version

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

       public MyDeque() {}

       public boolean isEmpty() {return false;}

       public int size() {return 0;}

       public void pushLeft(Item item) {}

       public void pushRight(Item item) {}

       public Item popLeft() {return null;}

       public Item popRight() {return null;}

   

    // 1.3.50

       public Iterator<Item> iterator() {return null;}

      

       // 1.3.47 -- you can destroy "that"

       public void concat(MyDeque<Item> that) {}

      

       // Write a test to ensure that your methods work!

       public static void main (String args[]) {}

}

Below are the the three methods that need to be added to this class. Also a test needs to be written to ensure methods work.

1.3.50 Fail-fast iterator. Modify the iterator code in Stack to immediately throw a

j ava.util.ConcurrentModificationException if the client modifies the collection

(via push() or pop()) during iteration? b).

Solution: Maintain a counter that counts the number of push() and pop() operations.

When creating an iterator, store this value as an Iterator instance variable. Before

each call to hasNext() and next(), check that this value has not changed since construction

of the iterator; if it has, throw the exception.

1.3.47 Catenable queues, stacks, or steques. Add an extra operation catenation that (destructively) concatenates two queues, stacks, or steques (see Exercise 1.3.32). Hint : Use a circular linked list, maintaining a pointer to the last item.

Important: Need to write a method to ensure methods work.

A double-ended queue or deque (pronounced "deck") is like a stack or a queue but supports adding and removing items at both ends. A deque stores a collection of items and supports the following API: Write a class Deque that uses a doubly-linked list to implement this API and a class ResizingArrayDeque that uses a resizing array.

Explanation / Answer

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

public class MyDeque<Item> implements Iterable<Item> {
  
private Node<Item> first;
private Node<Item> last;
private int N;
  
private static class Node<Item> {
Item item;
Node<Item> next;
Node<Item> prev;
}
  
public MyDeque () {
first = null;
last = null;
N = 0;
}
  
public boolean isEmpty () {return first == null || last == null;}
  
public int size () { return N;}
  
public void pushLeft (Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
first.prev = null;
  
if(isEmpty()) last = first;
else oldfirst.prev = first;
N++;
}
  
public void pushRight (Item item) {
Node<Item> oldlast = last;
last = new Node<Item>();
last.item = item;
last.prev = oldlast;
last.next = null;
  
if(isEmpty()) first = last;
else oldlast.next = last;
N++;
}
  
public Item popLeft () {
Item popItem = first.item;
if(N <= 1){
first = null;
last = null;
}
else{
first = first.next;
first.prev = null;
}
N--;
return popItem;
}
  
public Item popRight () {
Item popItem = last.item;
if(N <= 1){
first = null;
last = null;
}
else{
last = last.prev;
last.next = null;
}
N--;
return popItem;
}
  
public Iterator<Item> iterator () { return new ListIterator (); }
public class ListIterator implements Iterator<Item> {
private Node<Item> current = first;
public void remove () {}

public boolean hasNext () { return current != null; }
  
public Item next () {
Item item = current.item;
current = current.next;
return item;
}
}
  
public void concat (MyDeque<Item> that) {
if (!that.isEmpty()){
this.last.next = that.first;
this.last.next.prev = this.last;
this.last = that.last;
this.N += that.N;
  
that.first = null;
that.last = null;
that.N = 0;
}

}
  
public Item delete (int k) {
int counter = 0;
Node<Item> nodeDelete = this.first;
if(this.isEmpty()) return null;
while(counter < k){
nodeDelete = nodeDelete.next;
counter++;
}
Item res = nodeDelete.item;
if(nodeDelete == first){
nodeDelete = nodeDelete.next;
nodeDelete.prev = null;
first = nodeDelete;
}
else if(nodeDelete == last){
nodeDelete = nodeDelete.prev;
nodeDelete.next = null;
last = nodeDelete;
}
else{
Node<Item> nodePrev = nodeDelete.prev;
nodePrev.next = nodePrev.next.next;
nodeDelete = nodeDelete.next;
nodeDelete.prev = nodePrev;
}
N--;
return res;
}

public String toString () {
if (isEmpty ()) return "[]";
StringBuilder sb = new StringBuilder ("[");
Iterator<Item> i = iterator ();
sb.append (i.next ());
while (i.hasNext ()) {
sb.append (" ");
sb.append (i.next ());
}
sb.append ("]");
return sb.toString ();
}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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