The Deque ADT

Solution

A deque is a collection where a client can add, remove, and look at items at either end, the first end and the last end, but not in the middle. addFirst adds an item at the first end and addLast adds an item at the last end. removeFirst removes the item at the first end and removeLast removes the item at the last end. getFirst returns the item at the first end without removing it, and getLast does the same at the last end. isEmpty reports whether the deque has no items.

Solution

getFirst returns 5 and getLast returns 8.

Solution

For a stack, add and remove at the same end: addFirst is push and removeFirst is pop, with getFirst as top. For a queue, add at one end and remove from the other: addLast is enqueue and removeFirst is dequeue, with getFirst as front. For the stack, using the last end for all three operations works just as well. For the queue, adding at the first end and removing from the last end works just as well.

Exercise

Write a class DequeStack<T> that implements this Stack interface by storing the items in a Deque<T> field:

public interface Stack<T> {
  void push(T item);  // throws IllegalArgumentException if item is null
  void pop();         // throws NoSuchElementException if the stack is empty
  T top();            // throws NoSuchElementException if the stack is empty
  boolean isEmpty();
}

Assume ArrayDeque<T> and LinkedDeque<T> both implement Deque<T>, and that the Deque operations already throw these same exceptions in the same situations.

Solution

public class DequeStack<T> implements Stack<T> {
  private Deque<T> items = new ArrayDeque<>();

  @Override
  public void push(T item) {
    items.addFirst(item);
  }

  @Override
  public void pop() {
    items.removeFirst();
  }

  @Override
  public T top() {
    return items.getFirst();
  }

  @Override
  public boolean isEmpty() {
    return items.isEmpty();
  }
}

Using the last end for all three operations works as well.

Solution

removeFirst, removeLast, getFirst, and getLast. There is no item at either end to remove or return, so all four throw a NoSuchElementException. Adding null at either end throws an IllegalArgumentException.

Solution

The record needs removal at both ends: the newest page is removed when the user presses Back, and the oldest page is removed when the record is over its limit. A stack only removes the newest and a queue only removes the oldest. A deque supports both, and it still stops any part of the program from touching pages in the middle, which a general list would allow.