Queues, Deques, and Priority Queues - Data Structures and Abstractions with Java - page 257

LISTING 10-4

An interface for the ADT deque

public interface DequeInterface<T>
{

public void addToFront(T newEntry);
public void addToBack(T newEntry);
public T removeFront();
public T removeBack();
public T getFront();
public T getBack();
public boolean isEmpty();
public void clear();
} // end DequeInterface

A comparison of the operations that add, remove, and retrieve the entries of a stack, queue, and
deque is provided in Figure 10-11.

FIGURE 10-11

A comparison of operations for a stack s , a queue q , and a deque d :
(a) add; (b) remove; (c) retrieve

The stack s , queue q , or deque d

s.push(item)
d.addToFront(item)

q.enqueue(item)
d.addToBack(item)

(a) Add

Front (top)

Back

s.pop()
q.dequeue()
d.removeFront()

(b) Remove

d.removeBack()

Front (top) Back

s.peek()
q.getFront
d.getFront()

(c) Retrieve

d.getBack()

Front (top)

Back

Question 3 After the following nine statements execute, what string is at the front of the
deque and what string is at the back?
DequeInterface<String> myDeque = new LinkedDeque<String>();
myDeque.addToFront("Jim");
myDeque.addToBack("Jess");
myDeque.addToFront("Jill");
myDeque.addToBack("Jane");
String name = myDeque.getFront();
myDeque.addToBack(name);
myDeque.removeFront();
myDeque.addToFront(myDeque.removeBack());