Java Reference
In-Depth Information
look for concrete implementations of the abstract array type. You won't be fooled into
using a
LinkedList
, even though the
LinkedList
class actually provides
get
and
set
methods.
In the next section, you will see additional examples of abstract data types.
S
ELF
C
HECK
6.
What is the advantage of viewing a type abstractly?
7.
How would you sketch an abstract view of a doubly linked list? A
concrete view?
8.
How much slower is the binary search algorithm for a linked list
compared to the linear search algorithm?
685
686
15.4 Stacks and Queues
In this section we will consider two common abstract data types that allow insertion
and removal of items at the ends only, not in the middle. A stack lets you insert and
remove elements at only one end, traditionally called the top of the stack. To visualize
a stack, think of a stack of topics (see
Figure 12
).
A stack is a collection of items with Ȓlast in first outȓ retrieval.
New items can be added to the top of the stack. Items are removed at the top of the
stack as well. Therefore, they are removed in the order that is opposite from the order
in which they have been added, called last in, first out or LIFO order. For example, if
you add items
A
,
B
, and
C
and then remove them, you obtain
C
,
B
, and
A
.
Traditionally, the addition and removal operations are called
push
and
pop
.
A queue is a collection of items with Ȓfirst in first outȓ retrieval.
A queue is similar to a stack, except that you add items to one end of the queue (the
tail) and remove them from the other end of the queue (the head). To visualize a
queue, simply think of people lining up (see
Figure 13
). People join the tail of the
queue and wait until they have reached the head of the queue. Queues store items in a
