设计模式之不变设计模式(三)
nd for
return stack;
}// end else
}// end reverse()
@Override
public Iterator iterator() {
return new Iterator() {
private PersistentStack stack = PersistentStack.this;
@Override
public boolean hasNext() {
return !stack.isEmpty();
}
@Override
public E next() {
if (!hasNext())
throw new NoSuchElementException();
E e = stack.head;
stack = stack.tail;
return e;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
} // end class PersistentStack
不变队列实现
[java]
/**
* The Queue class represents an immutable first-in-first-out (FIFO) queue of
* objects. Use two @see PersistentStack to implement the persistent queue.
* Every element is pushed on the incoming stack once, popped off the incoming
* stack once, pushed on the outgoing stack once and popped off the outgoing
* stack once. enqueue(E) is O(1). Dequeuing is on average O(1), though it is
* O(n) for a single case which only few happens when reverse incoming stack
* elements into outgoing stack.
*
* @author E-mail:yangzhonglive@gmail.com
* @version 2013-10-12
* @since 1.0
* @param
*/
public class PersistentQueue {
// ----------------------------------------------------
// ---private properties
// ----------------------------------------------------
/**
* Add elements in this stack when add elements in this persistent queue
*/
private final PersistentStack incoming;
/**
* Remove elements from this stack when remove elements from this persistent
* queue
*/
private final PersistentStack outgoing;
// ----------------------------------------------------
// ---constructor
// ----------------------------------------------------
/**
* requires default constructor. Initial an empty persistent queue.
*/
public PersistentQueue() {
incoming = new PersistentStack();
outgoing = new PersistentStack();
}
/**
* Construct a new persistent queue based on the input persistent queue.
*
* @param outgoing
* @param incoming
*/
public PersistentQueue(PersistentStack outgoing,
PersistentStack incoming) {
this.outgoing = outgoing;
this.incoming = incoming;
}
// ----------------------------------------------------
// ---API
// ----------------------------------------------------
/**
* Returns the queue that adds an item into the tail of this queue without
* modifying this queue.
*
*
* e.g.
* When this queue represents the queue (2, 1, 2, 2, 6) and we enqueue the value 4 into this queue,
* this method returns a new queue (2, 1, 2, 2, 6, 4)
* and this object still represents the queue (2, 1, 2, 2, 6) .
*
*
* If the element e is null, throws IllegalArgumentException.
*
*
* How to enqueue works:
* add element into incoming stack.
*
*