Deque

A deque is a sequence with access to both ends. Unlike a stack, it can push, peek, and pop on the left or the right. Unlike a conventional queue, neither end has a fixed role. An immutable deque returns a new deque when an operation would otherwise change its contents; the previous version remains available. section 3.1

public interface IDeque<T> : IEnumerable<T>
{
    IDeque<T> PushLeft(T item);
    IDeque<T> PushRight(T item);
    IDeque<T> PopLeft();
    IDeque<T> PopRight();
    T Left();
    T Right();
    bool IsEmpty { get; }
}

The C# interface names the four push/pop operations, two peeks, and an emptiness check. It also makes the deque enumerable from left to right. section 3.1

Why not link a list in both directions? A naïve immutable design stores a left item, a middle deque, and a right item. Its operations can produce the right answers, but a push or pop may rebuild the nested middle rather than reuse large parts of the old version. Two stacks have a different problem: obtaining cheap access at both ends requires too many reversals. Correct end operations alone do not guarantee an efficient persistent deque. section 3.2 section 3.0

A finger-tree design puts small buffers, called minis, at the edges and a recursive deque in the middle. Each edge mini holds one to four items; the middle holds minis rather than individual items. If an edge has room, a push changes only that mini and reuses the rest. If a four-item mini overflows, three of its items become one chunk pushed into the middle. A pop usually shrinks an edge mini; when it cannot, it draws a chunk from the middle or handles the remaining small deque explicitly. section 3.3.2

public sealed class Deque<T> : IDeque<T>
{ […]
    private readonly IMini left;
    private readonly IDeque<IMini> middle; #1
    private readonly IMini right;

    private Deque(IMini left, IDeque<IMini> middle, IMini right)
    {
        this.left = left;
        this.middle = middle;
        this.right = right;
    }

    public IDeque<T> PushLeft(T value) => 
        left.Size < 4 ?
            new Deque<T>(left.PushLeft(value), middle, right) :
            new Deque<T>(
                new Two(value, left.Left()),
                middle.PushLeft(left.PopLeft()), #2
                right);

    public IDeque<T> PushRight(T value) => 
        right.Size < 4 ? 
            new Deque<T>(left, middle, right.PushRight(value)) :
            new Deque<T>(
                left,
                middle.PushRight(right.PopRight()), #3
                new Two(right.Right(), value));

    public IDeque<T> PopLeft()
    {
        if (left.Size > 1)
            return new Deque<T>(left.PopLeft(), middle, right);
        if (!middle.IsEmpty)
            return new Deque<T>(middle.Left(), middle.PopLeft(), right);
        if (right.Size > 1)
            return new Deque<T>(
                new One(right.Left()), middle, right.PopLeft());
        return new SingleDeque(right.Left());
    }

    public IDeque<T> PopRight()
    {
        if (right.Size > 1)
            return new Deque<T>(left, middle, right.PopRight());
        if (!middle.IsEmpty)
            return new Deque<T>(left, middle.PopRight(), middle.Right());
        if (left.Size > 1)
            return new Deque<T>(
                left.PopRight(), middle, new One(left.Right()));
        return new SingleDeque(left.Right());
    }

    public T Left() => left.Left();
    public T Right() => right.Right();
    public bool IsEmpty => false;

    public IEnumerator<T> GetEnumerator()
    {
        foreach (var item in left) 
            yield return item;
        foreach (var mini in middle)
            foreach(var item in mini)
                yield return item;
        foreach (var item in right)
            yield return item;
    }
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

The C# implementation shows the key invariant in code: a full edge sends a chunk inward, while an edge with room leaves the middle untouched. section 3.3.2

Figure 3.5 A 22-item deque. The left mini on the second level has overflowed, so we’ve made a single-item deque of minis of minis to hold three Threes. Notice that the number of arrows traversed from the root to any given leaf is shallowest at the left and right edges and deepest in the middle.

The 22-item diagram makes the shape visible: paths from the root are shortest at the edges and deepest toward the middle. section 3.4

This chunking preserves much of each old version. Most operations take O(1) on average; an operation that propagates through the tree takes O(log n) time and extra memory in the worst case. The recursive middle also has a more deeply nested generic type at each level. In C#, those levels remain manageable: their number grows logarithmically with the deque’s size. section 3.10 section 3.6

Concatenation is another reason to use the tree. Repeatedly pushing every item from one deque into another is linear. Instead, the edge minis can be regrouped into two- or three-item chunks, and the two middles concatenated recursively. Allowing both two- and three-item chunks in the middle makes genuinely sublinear concatenation possible. section 3.7 section 3.0

A mutable deque can serve a different purpose: an undo–redo queue can add at one end and remove at the other, recording inverse commands for each change. That works, but every undoable mutation needs corresponding undo and redo commands. The immutable design instead keeps earlier versions available through persistence. section 2.6.2 section 3.10