Immutability in C# Part Four: An Immutable Queue - Fabulous Adventures In Coding - Site Home - MSDN Blogs
public sealed class Queue<T> : IQueue<T>
{
private sealed class EmptyQueue : IQueue<T>
{
public bool IsEmpty { get { return true; } }
public T Peek () { throw new Exception("empty queue"); }
public IQueue<T> Enqueue(T value)
{
return new Queue<T>(Stack<T>.Empty.Push(value), Stack<T>.Empty);
}
public IQueue<T> Dequeue() { throw new Exception("empty queue"); }
public IEnumerator<T> GetEnumerator() { yield break; }
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
}
private static readonly IQueue<T> empty = new EmptyQueue();
public static IQueue<T> Empty { get { return empty; } }
public bool IsEmpty { get { return false; } }
private readonly IStack<T> backwards;
private readonly IStack<T> forwards;
private Queue(IStack<T> f, IStack<T> b)
{
forwards = f;
backwards = b;
}
public T Peek() { return forwards.Peek(); }
public IQueue<T> Enqueue(T value)
{
return new Queue<T>(forwards, backwards.Push(value));
}
public IQueue<T> Dequeue()
{
IStack<T> f = forwards.Pop();
if (!f.IsEmpty)
return new Queue<T>(f, backwards);
else if (backwards.IsEmpty)
return Queue<T>.Empty;
else
return new Queue<T>(backwards.Reverse(), Stack<T>.Empty);
}
public IEnumerator<T> GetEnumerator()
{
foreach (T t in forwards) yield return t;
foreach (T t in backwards.Reverse()) yield return t;
}
IEnumerator IEnumerable.GetEnumerator() {return this.GetEnumerator(); }
}
}
public class PersistentQueue<E> {
* This is the internal immutable stack.
private static class PersistentStack<E> {
private E head;
private PersistentStack<E> tail;
private int size;
private PersistentStack(E obj, PersistentStack<E> tail) {
this.head = obj;
this.tail = tail;
this.size = tail.size + 1;
}
public static PersistentStack emptyStack() {
return new PersistentStack();
}
private PersistentStack() {
this.head = null;
this.tail = null;
this.size = 0;
}
* Get a new reversed stack.
public PersistentStack<E> toReverseStack() {
PersistentStack<E> stack = new PersistentStack<E>();
PersistentStack<E> tail = this;
while (!tail.isEmpty()) {
stack = stack.push(tail.head);
tail = tail.tail;
}
return stack;
}
public boolean isEmpty() {
return this.size == 0;
}
public PersistentStack<E> push(E obj) {
return new PersistentStack<E>(obj, this);
}
}
private PersistentStack<E> order;
/**
* The reverse stack of order
*/
private PersistentStack<E> reverse;
private PersistentQueue(PersistentStack<E> order, PersistentStack<E> reverse) {
this.order = order;
this.reverse = reverse;
}
/**
* requires default constructor.
*/
public PersistentQueue() {
this.order = PersistentStack.emptyStack();
this.reverse = PersistentStack.emptyStack();
}
* Returns the queue that adds an item into the tail of this queue without
* modifying this queue.
* 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)
public PersistentQueue<E> enqueue(E e) {
if (null == e)
throw new IllegalArgumentException();
return new PersistentQueue<E>(this.order.push(e), this.reverse);
}
/**
* Returns the queue that removes the object at the head of this queue
* without modifying this queue.
*
* <pre>
* e.g.
* When this queue represents the queue (7,1,3,3,5,1) .
* this method returns a new queue (1,3,3,5,1)
* and this object still represents the queue (7,1,3,3,5,1)
* </pre>
*
* If this queue is empty, throws java.util.NoSuchElementException.
*
* @param e
* @return
*/
public PersistentQueue<E> dequeue() {
if (this.isEmpty())
throw new NoSuchElementException();
if (!this.reverse.isEmpty()) {
return new PersistentQueue<E>(this.order, this.reverse.tail);
} else {
// revers the ordered stack then "clean" that stack
return new PersistentQueue<E>(PersistentStack.emptyStack(),
this.order.toReverseStack().tail);
}
}
/**
* This method simply reverse the order stack and assign it to reverse
* stack, the internal queue is not modified, it is necessary since all new
* objects are enqueued to order stack, while peek() looking at the reverse
* stack, we do not want to reverse the order stack again and again while
* looking for the head of reverse when it is empty.
*/
private void balanceQueue() {
this.reverse = this.order.toReverseStack();
this.order = PersistentStack.emptyStack();
}
public E peek() {
if (this.isEmpty())
throw new NoSuchElementException();
if (this.reverse.isEmpty())
balanceQueue();
return this.reverse.head;
}
public boolean isEmpty() {
return size() == 0;
}
public int size() {
return this.order.size + this.reverse.size;
}
}
用上一篇文章的immutable stack 来实现 immutable queue.
其实就是用两个栈实现队列，具体的思想可以参考 编程之美。。
注意：代码中析构函数那一段代码的目的主要是为了避免析构函数递归调用时递归深度太大。。
通过将链表后序的节点的智能指针复制到局部的vector中，通过vector的析构函数自动调用成员的析构函数的规则来实现。。
附加题:
实现一个reverse操作（这道题据说坑了不少同学，其实非常地简单，一句话就能搞定）
https://en.wikipedia.org/wiki/Persistent_data_structure
The first insight we need is that a stack is essentially a “backwards” queue. Because I think it will come in handy later, I’m going to declare an extension method right now which takes a stack and reverses it:
static public IStack<T> Reverse<T>(this IStack<T> stack )
{
IStack<T> r = Stack<T>.Empty;
for (IStack<T> f = stack; !f.IsEmpty; f = f.Pop())
r = r.Push(f.Peek());
return r;
}
So let’s keep two stacks around, one in “forwards” order, ready to be dequeued, and one in “backwards” order, ready to be enqueued. If we go to dequeue and find that the forward stack is empty, only then will we reverse the backwards stack.{
IStack<T> r = Stack<T>.Empty;
for (IStack<T> f = stack; !f.IsEmpty; f = f.Pop())
r = r.Push(f.Peek());
return r;
}
public sealed class Queue<T> : IQueue<T>
{
private sealed class EmptyQueue : IQueue<T>
{
public bool IsEmpty { get { return true; } }
public T Peek () { throw new Exception("empty queue"); }
public IQueue<T> Enqueue(T value)
{
return new Queue<T>(Stack<T>.Empty.Push(value), Stack<T>.Empty);
}
public IQueue<T> Dequeue() { throw new Exception("empty queue"); }
public IEnumerator<T> GetEnumerator() { yield break; }
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
}
private static readonly IQueue<T> empty = new EmptyQueue();
public static IQueue<T> Empty { get { return empty; } }
public bool IsEmpty { get { return false; } }
private readonly IStack<T> backwards;
private readonly IStack<T> forwards;
private Queue(IStack<T> f, IStack<T> b)
{
forwards = f;
backwards = b;
}
public T Peek() { return forwards.Peek(); }
public IQueue<T> Enqueue(T value)
{
return new Queue<T>(forwards, backwards.Push(value));
}
public IQueue<T> Dequeue()
{
IStack<T> f = forwards.Pop();
if (!f.IsEmpty)
return new Queue<T>(f, backwards);
else if (backwards.IsEmpty)
return Queue<T>.Empty;
else
return new Queue<T>(backwards.Reverse(), Stack<T>.Empty);
}
public IEnumerator<T> GetEnumerator()
{
foreach (T t in forwards) yield return t;
foreach (T t in backwards.Reverse()) yield return t;
}
IEnumerator IEnumerable.GetEnumerator() {return this.GetEnumerator(); }
}
}
very element (except the first one) is pushed on the backwards stack once, popped off the backwards stack once, pushed on the forwards stack once and popped off the forwards stack once. If you enqueue a thousand items and then dequeue two, yes, the second dequeue will be expensive as the backwards list is reversed, but the 998 dequeues following it will be cheap. That’s unlike our earlier implementation, where every dequeue was potentially expensive. Dequeuing is on average O(1), though it is O(n) for a single case.
The problem with the immutable queue shown in the above video is that it procrastinates. Instead of continuously doing small amounts of work, it delays doing anything until the last possible moment. When the outgoing item stack is empty, and someone wants to dequeue an item, the entire state must be reversed. A constant time queue will need to be constantly doing that sort of work as items are enqueued and dequeued, instead of all at once.
The first necessary change is obvious: we must incrementally reverse the incoming stack into the outgoing stack whenever an item is enqueued or dequeued. Because we can only add items to the top of the outgoing stack (since it’s a stack), not the bottom, we’ll have to have a ‘ready to dequeue’ outgoing stack and a ‘partially rebuilt’ outgoing stack. Whenever an item is enqueued or dequeued, we’ll reverse a few more items onto the partially rebuilt outgoing stack. Once the partially rebuilt outgoing stack is completely rebuilt, we’ll replace the true outgoing stack.
The second necessary change is a consequence of the first. The incoming stack is no longer being reduced (its items are needed in the same order for the next outgoing stack rebuilding pass). Garbage will accumulate at the bottom of the incoming stack. We can ignore it by keeping a count and artificially decrementing it but, unless we want memory usage to go up without bound, those nodes eventually need to be cleaned up. To make that possible, the incoming queue will also have to be continuously iteratively rebuilt.
* This is the internal immutable stack.
private static class PersistentStack<E> {
private E head;
private PersistentStack<E> tail;
private int size;
private PersistentStack(E obj, PersistentStack<E> tail) {
this.head = obj;
this.tail = tail;
this.size = tail.size + 1;
}
public static PersistentStack emptyStack() {
return new PersistentStack();
}
private PersistentStack() {
this.head = null;
this.tail = null;
this.size = 0;
}
* Get a new reversed stack.
public PersistentStack<E> toReverseStack() {
PersistentStack<E> stack = new PersistentStack<E>();
PersistentStack<E> tail = this;
while (!tail.isEmpty()) {
stack = stack.push(tail.head);
tail = tail.tail;
}
return stack;
}
public boolean isEmpty() {
return this.size == 0;
}
public PersistentStack<E> push(E obj) {
return new PersistentStack<E>(obj, this);
}
}
private PersistentStack<E> order;
/**
* The reverse stack of order
*/
private PersistentStack<E> reverse;
private PersistentQueue(PersistentStack<E> order, PersistentStack<E> reverse) {
this.order = order;
this.reverse = reverse;
}
/**
* requires default constructor.
*/
public PersistentQueue() {
this.order = PersistentStack.emptyStack();
this.reverse = PersistentStack.emptyStack();
}
* Returns the queue that adds an item into the tail of this queue without
* modifying this queue.
* 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)
public PersistentQueue<E> enqueue(E e) {
if (null == e)
throw new IllegalArgumentException();
return new PersistentQueue<E>(this.order.push(e), this.reverse);
}
/**
* Returns the queue that removes the object at the head of this queue
* without modifying this queue.
*
* <pre>
* e.g.
* When this queue represents the queue (7,1,3,3,5,1) .
* this method returns a new queue (1,3,3,5,1)
* and this object still represents the queue (7,1,3,3,5,1)
* </pre>
*
* If this queue is empty, throws java.util.NoSuchElementException.
*
* @param e
* @return
*/
public PersistentQueue<E> dequeue() {
if (this.isEmpty())
throw new NoSuchElementException();
if (!this.reverse.isEmpty()) {
return new PersistentQueue<E>(this.order, this.reverse.tail);
} else {
// revers the ordered stack then "clean" that stack
return new PersistentQueue<E>(PersistentStack.emptyStack(),
this.order.toReverseStack().tail);
}
}
/**
* This method simply reverse the order stack and assign it to reverse
* stack, the internal queue is not modified, it is necessary since all new
* objects are enqueued to order stack, while peek() looking at the reverse
* stack, we do not want to reverse the order stack again and again while
* looking for the head of reverse when it is empty.
*/
private void balanceQueue() {
this.reverse = this.order.toReverseStack();
this.order = PersistentStack.emptyStack();
}
public E peek() {
if (this.isEmpty())
throw new NoSuchElementException();
if (this.reverse.isEmpty())
balanceQueue();
return this.reverse.head;
}
public boolean isEmpty() {
return size() == 0;
}
public int size() {
return this.order.size + this.reverse.size;
}
}
用上一篇文章的immutable stack 来实现 immutable queue.
其实就是用两个栈实现队列，具体的思想可以参考 编程之美。。
注意：代码中析构函数那一段代码的目的主要是为了避免析构函数递归调用时递归深度太大。。
通过将链表后序的节点的智能指针复制到局部的vector中，通过vector的析构函数自动调用成员的析构函数的规则来实现。。
附加题:
实现一个reverse操作（这道题据说坑了不少同学，其实非常地简单，一句话就能搞定）
https://en.wikipedia.org/wiki/Persistent_data_structure
a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure.
A data structure is partially persistent if all versions can be accessed but only the newest version can be modified. The data structure is fully persistent if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called confluently persistent. Structures that are not persistent are called ephemeral.
Read full article from Immutability in C# Part Four: An Immutable Queue - Fabulous Adventures In Coding - Site Home - MSDN Blogs