Section 3.17 Implementing a Deque in Java
As we have done in previous sections, we will create a new class for the implementation of the abstract data type deque. Again, the Java ArrayList will provide a very nice set of methods upon which to build the details of the deque. Our implementation (Listing 3.17.1) will assume that the tail of the deque is at position 0 in the list.
import java.util.ArrayList;
import java.util.NoSuchElementException;
class Deque<T> {
/*
* The tail of the deque is at the beginning
* of the ArrayList; the head is the last item
*/
ArrayList<T> items;
/*
* Create a new Deque
*/
public Deque() {
this.items = new ArrayList<T>();
}
/*
* Returns true if there are no items in the deque;
* false otherwise.
*/
public boolean isEmpty() {
return (this.items.isEmpty());
}
/*
* Add an item to the head of the deque
*/
public void addHead(T item) {
this.items.add(item);
}
/*
* Add an item to the tail of the deque
*/
public void addTail(T item) {
this.items.add(0, item);
}
/*
* Remove the item at the head of the deque and return it.
* If the deque is empty, throws an exception.
*/
public T removeHead() {
if (this.isEmpty()) {
throw new NoSuchElementException("Deque is empty.");
}
return this.items.remove(this.size() - 1);
}
/*
* Remove the item at the tail of the deque and return it.
* If the deque is empty, throws an exception.
*/
public T removeTail() {
if (this.isEmpty()) {
throw new NoSuchElementException("Deque is empty.");
}
return this.items.remove(0);
}
/*
* Return the item at the head of the deque, but do not remove it.
* If the deque is empty, throws an exception.
*/
public T peekHead() {
if (this.isEmpty()) {
throw new NoSuchElementException("Deque is empty.");
}
return this.items.get(this.size() - 1);
}
/*
* Return the item at the tail of the deque, but do not remove it.
* If the deque is empty, throws an exception.
*/
public T peekTail() {
if (this.isEmpty()) {
throw new NoSuchElementException("Deque is empty.");
}
return this.items.get(0);
}
/*
* Returns the number of items in the deque.
*/
public int size() {
return this.items.size();
}
/*
* Convert to string as an array from tail to head
*/
public String toString() {
if (!this.items.isEmpty()) {
String arrString = this.items.toString();
return "tail " + arrString + " head";
} else {
return "<<empty deque>>";
}
}
}
Listing 3.17.2 shows a deque in action as we perform the sequence of operations from Section 3.16.
And here is its output:
d.isEmpty() | true | <<empty deque>> d.addTail(4) | | tail [4] head d.addTail(505) | | tail [505, 4] head d.addHead(1066) | | tail [505, 4, 1066] head d.addHead(4711) | | tail [505, 4, 1066, 4711] head d.size | 4 | tail [505, 4, 1066, 4711] head d.isEmpty() | false | tail [505, 4, 1066, 4711] head d.addTail(217) | | tail [217, 505, 4, 1066, 4711] head d.removeTail() | 217 | tail [505, 4, 1066, 4711] head d.removeHead() | 4711 | tail [505, 4, 1066] head
You can see many similarities to Java code already described for stacks and queues. You are also likely to observe that in this implementation adding and removing items from the head is \(O(1)\) whereas adding and removing from the tail is \(O(n)\text{.}\) This is to be expected, given the common operations that appear for adding and removing items. Again, the important thing is to be certain that we know where the head and tail are assigned in the implementation.
You have attempted of activities on this page.
