Iteration
Say we want to support iteration over our stack items from the client but we don’t want to reveal the internal representation (array or LinkedList) of the stack. Java provides a nice solution to this called iteration. This can be applied to multiple data structures (no matter which implementation we use).
Iterable
Section titled “Iterable”An Iterable
is a class that has a method that returns an Iterator
.
public interface Iterable<Item>{ Iterator<Item> iterator();}
Iterator
Section titled “Iterator”Has methods hasNext()
and next()
, Java also allows remove however this could lead to insidious debugging problems.
public interface Iterator<Item>{ boolean hasNext(); Item next(); //optional and risky void remove();}
Why make Data structures Iterable
Section titled “Why make Data structures Iterable”Providing an option to make our data structures Iterable
ensures we support an elegant and clean approach to our client. A long form of code without an Iterable
structure could look like:
Iterator<String> i = stack.iterator();while (i.hasNext()){ String s = i.next(); StdOut.prinln(s);}
where as a shorthand version of this could be as simple as:
for(String s: stack){ StdOut.println(s);}
Stack Iterator: Linked-list implementation
Section titled “Stack Iterator: Linked-list implementation”import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>{ ... public Iterator<Item> iterator() { return new ListIterator(); } private class ListIterator implements Iterator<Item>{ private Node current = first; public boolean hasNext() { return current != null;} public void remove() { /* Not Supported */ } public Item next() { Item item = current.item; current = current.next; return item;
} }}
Stack Iterator: array implementation
Section titled “Stack Iterator: array implementation”import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>{ ... public Iterator<Item> iterator() { return new ReverseArrayIterator(); } private class ReverseArrayIterator implements Iterator<Item>{ private int i = N; public boolean hasNext() { return i > 0;} public void remove() { /* Not Supported */ } public Item next() { return s[--i]; } }}
Bag Data Structure
Section titled “Bag Data Structure”For a lot of clients the order of inserting and removing data into our collection is not important leading us to the bag data structure.
Bag() // create an empty arrayvoid add(Item x) //insert a new item onto bagint size() number of items in bagIterable<Item> iterator() //iterator for all items in bag
The bag API is a simple narrow set of operations not putting any focus on order of items in the collection utilising only add operations. For a stack this would be the same without the pop()
operation and for queue this would be the same without the dequeue()
operation.