Java Reference
In-Depth Information
this.next = next;
}
}
A queue then consists of a reference to the head and tail cells and the
implementation of
add
and
remove
.
public class SingleLinkQueue {
protected Cell head;
protected Cell tail;
public void add(Object item) {/* ... */}
public Object remove() {/* ... */}
}
We make the
head
and
tail
references
protected
so that extended classes
can manipulate the linked-list cells directly, rather than having to use
add
and
remove
which would involve wrapping and unwrapping the ele-
ments each time.
One group decides that it needs a priority queue in which items are
stored in a specific order rather than always being inserted at the tail.
So it defines a
PriorityQueue
class in another package that extends
SingleLinkQueue
and overrides
add
to insert the object in the right place.
The
PriorityQueue
class's implementation of
add
can access the
head
and
tail
fields inherited from
SingleLinkQueue
the code is in a subclass of
SingleLinkQueue
and the type of the object reference used (
this
) is the
same as that subclass, namely
PriorityQueue
, so access to the
protected
members is allowed. This is what you would expect.
The group designing the priority queue needs an additional featureit
wants to be able to merge two priority queues. In a merge operation
the target queue ends up with the elements of both queues, while the
queue with which it was merged becomes empty. The
merge
operation
starts like this: