Transcript Iterator

Chapter 5
Array-Based
Structures
© 2006 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
Overview
●
General-Purpose Array-Based Structures
–
5.1 Getting around fixed length arrays
–
5.2 Stack and Queue interfaces
–
5.3 List interface and the ArrayList class
–
5.4 List traversal
Shrinking and Stretching Arrays
●
●
Array lengths are determined and fixed when
allocated.
Many times implementations require variable
lengths of items.
Shrinking and Stretching Arrays
●
A Deck holds a varying number of Cards, fewer
as Cards are dealt.
Shrinking and Stretching Arrays
●
A Card has two fields, rank and suit.
Shrinking and Stretching Arrays
Shrinking and Stretching Arrays
Shrinking and Stretching Arrays
Shrinking and Stretching Arrays
●
●
By specifying a size, we can limit the range of
available elements.
The Deck capacity remains unchanged at 52.
Shrinking and Stretching Arrays
Shrinking and Stretching Arrays
●
Getting the number of Cards in the Deck and
testing for an empty Deck are trivial. i.e. get the
size variable.
Shrinking and Stretching Arrays
●
●
Only method to modify the size is the deal()
method which removes and returns one
Card from the Deck.
size is decremented but the array still
references the last element.
Shrinking and Stretching Arrays
●
●
shuffle() should position the Cards randomly
through the Deck.
For each position in the Deck, randomly select
another position in the Deck and swap Cards.
Shrinking and Stretching Arrays
●
●
What if a structure needs to grow beyond its
original capacity?
Copy the entire contents of the array into a new,
larger array.
Implementing Stacks and Queues
●
ArrayStack Class
–
Similar to Deck class in that it contains an array
data and an int size.
Implementing Stacks and Queues
●
●
The isEmpty() method is identical to the one
from Deck.
The pop() method is similar to deal().
Implementing Stacks and Queues
●
The peek() method is simpler than pop().
Implementing Stacks and Queues
●
If the push() method is called when the data
array is full, the array must be streched.
Implementing Stacks and Queues
Implementing Stacks and Queues
●
ArrayQueueClass
–
●
Adding something to an ArrayQueue is exactly like
pushing it onto an ArrayStack.
Removing an element must cause the front of
the queue to move along the array.
Implementing Stacks and Queues
●
When insertions runs up against the right end of
the array, the queue must wrap around, so that
the next element added goes at position 0.
or
Implementing Stacks and Queues
Implementing Stacks and Queues
Implementing Stacks and Queues
The List Interface
●
●
●
Stacks and queues limit access to the data to
one end or the other.
The List Interface has a more general-purpose
use.
A List is similar to an array, but it does not have
a fixed size.
The List Interface
The List Interface
The List Interface
Input
Return Value
List
list.add("eggs");
[ eggs ]
list.add("bread");
[ eggs bread ]
list.add("tea");
[ eggs bread tea ]
list.contains("eggs");
true
[ eggs bread tea ]
list.contains("rutabagas");
false
[ eggs bread tea ]
list.get(1);
“bread”
[ eggs bread tea ]
list.isEmpty();
false
[ eggs bread tea ]
list.remove(0);
[ bread tea ]
list.remove("llamachow");
false
[ bread tea]
list.remove("tea");
true
[ bread ]
list.size();
1
[ bread ]
The List Interface
●
The ArrayList's structure is similar to the
ArrayStack and ArrayQueue.
The List Interface
●
●
Some methods are trivial:
–
get(int index)
–
set(int index, E target)
–
add(E target)
Some are identical to the ArrayStack methods:
–
isEmpty()
–
isFull()
–
size()
–
stretch()
The List Interface
●
contains() method searches the list for an
object.
The List Interface
●
remove() removes and returns the item at a
given location or removes the first occurrence of
a particular item, if any.
The List Interface
●
remove() shifts all subsequent elements one
place to the left.
Iterators
●
●
Often a List must be traversed.
Because, outside of the class, access to the
data is limited, an Iterator interface can be used
to traverse the List.
Iterators
Iterators
●
●
Iterator general use:
Warning: Each call to next() advances the
Iterator.
Iterators
●
●
java.util.NoSuchElementException
–
Thrown when the Iterator has reach it's end and
next() is called.
–
Avoided by preceding all next() calls by a hasNext()
test.
java.util.IllegalStateException
–
Thrown when next() has never been invoked, or
has not been invoked since the last invocation of
remove().
Iterators
●
●
The Iterable interface requires one method.
When using Iterators, an enhanced for loop can
be used.
Iterators
Iterators
●
●
●
●
The iterator() method for ArrayList creates an
instance of ArrayIterator.
The ArrayIterator references the ArrayList.
An int is also used to indicate how far down the
ArrayList we've traveled.
A previous index is useful to the remove()
method.
Iterators
Iterators
Iterators
Iterators
Iterators
Iterators
●
●
Keep going until the sum of the players’ scores
is 13.
A player keeps playing until he must “Go Fish”.
Iterators
Iterators
Iterators
●
●
The computerTurn() method is similar to
playerTurn() method but the rank is chosen
randomly.
Rather than repeat work to covert a number to a
rank, a Card of the rank in question is created
from the number. The suit doesn't matter
(HEARTS is arbitrarily specified).
Iterators
Iterators
Iterators
●
●
●
Both of the methods in the GoFishHand class
involve Iterators, so we import java.util.Iterator.
give() transfers all Cards of a given rank from
one hand to another and returns a boolean
indicating if any were transferred.
meldSets() removes all sets of 4 same-rank
Cards and returns the total number of sets.
Iterators
Iterators
Iterators
Java Collections Framework
Java Collections Framework
●
●
●
●
The java ArrayList is similar to the one
implemented in this chapter.
The Vector class is still present for backward
compatibility. New code should use the
ArrayList class.
The framework does not include a Stack
interface, but it does include a Stack class that
extends the Vector class.
There is a Queue interface, but no array-based
implementation.
Java Collections Framework
●
●
●
●
List is implemented by the class AbstractList.
Abstract class instances can only be created by
instantiating non-abstract classes that extend it.
An abstract class is similar to an interface in
that is defines abstract methods.
The difference is that abstract classes may
contain fields and non-abstract methods.
Java Collections Framework
Summary
●
●
●
●
Array sizes cannot be changed, but the arraybased structures can maintain varying sizes of
data.
Lists such as ArrayList provide basic methods
for accessing elements and return Iterators.
An Iterator allows us to traverse the List, visiting
each element.
Java’s collections framework includes a List
interface, an ArrayList class, a Stack class, and
a Queue interface.