Deque<T> Class

Definition

Namespace

Bodu.Collections.Generic

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

Deque{T}.cs

Represents a double-ended queue (deque) backed by a contiguous circular array. Elements may be added or removed from either end in amortized O(1) time. The AllowGrow property selects between growable and fixed-capacity behavior at runtime.

public sealed class Deque<T> : RingBackedCollection<T>, ICollection, IReadOnlyCollection<T>, IEnumerable<T>, IEnumerable

Type Parameters

T

Specifies the type of elements stored in the deque.

Inheritance

object

RingBackedCollection<T>

Deque<T>

Implements

ICollection

IReadOnlyCollection<T>

IEnumerable<T>

IEnumerable

Inherited Members

RingBackedCollection<T>.Clear()

RingBackedCollection<T>.Contains(T)

RingBackedCollection<T>.CopyTo(T[], int)

RingBackedCollection<T>.ToArray()

RingBackedCollection<T>.TrimExcess()

RingBackedCollection<T>.GetEnumerator()

RingBackedCollection<T>.Capacity

RingBackedCollection<T>.IsEmpty

RingBackedCollection<T>.IsFull

RingBackedCollection<T>.this[int]

RingBackedCollection<T>.Count

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

ComparableExtensions.AtLeast<T>(T, T, IComparer<T>)

ComparableExtensions.AtMost<T>(T, T, IComparer<T>)

ComparableExtensions.IsEqualTo<T>(T, T, IComparer<T>)

ComparableExtensions.Max<T>(T, T, IComparer<T>)

ComparableExtensions.Min<T>(T, T, IComparer<T>)

Examples

// Growable double-ended queue (the default).
var deque = new Deque<int>();
deque.AddLast(2);
deque.AddFirst(1);
deque.AddLast(3);                  // contents: 1, 2, 3
int head = deque.RemoveFirst();    // 1

// Fixed-capacity queue: rejects adds when full.
var bounded = new Deque<int>(capacity: 8, allowGrow: false);
for (int i = 0; i < 8; i++) bounded.AddLast(i);
bool added = bounded.TryAddLast(8); // false - bounded is full

Remarks

Deque<T> stores its elements in a single backing array using head and tail indices that wrap around modulo the capacity. This gives O(1) amortized cost for adds and removes at either end, plus O(1) random read access through the indexer in head-to-tail logical order.

The growth policy is controlled by the mutable AllowGrow property:

• AllowGrow = true (the default) - the backing array doubles automatically whenever AddFirst(T) or AddLast(T) would otherwise overflow, capped at MaxLength. TryAddFirst(T) and TryAddLast(T) always return true.
• AllowGrow = false - the deque is fixed at its current capacity and OverflowPolicy selects the behavior of adds on a full deque. Under Reject (the default), AddFirst(T) and AddLast(T) throw InvalidOperationException when full while TryAddFirst(T) and TryAddLast(T) return false without modifying state. Under EvictOpposite, adds silently discard the element at the opposite end to make room - the Python deque(maxlen=N) semantics, analogous to AllowOverwrite - raising ItemEvicting before and ItemEvicted after each eviction.

Key operations:

• AddFirst(T) / AddLast(T) - push at either end (with TryAddFirst(T) / TryAddLast(T) non-throwing variants).
• Inherited RemoveFirst / RemoveLast - pop and return the head or tail element.
• Inherited PeekFirst / PeekLast - read the head or tail element without removing it.
• EnsureCapacity(int) - pre-grow the backing array even when AllowGrow is false.
• Inherited TrimExcess() - shrink the backing array to Count after a burst of removes.

AllowGrow can be toggled at runtime to switch the deque between modes. Switching from true to false does not shrink the existing capacity - call TrimExcess() afterwards if a smaller footprint is wanted.

For a single-ended FIFO buffer with eviction-on-full semantics, see CircularBuffer<T>. For thread-safe concurrent FIFO access, see ConcurrentCircularBuffer<T> in the Bodu.Collections.Concurrent package. Deque<T> itself is not thread-safe; concurrent reads and writes require external synchronization.

Deque<T> accepts null values for reference types and allows duplicate elements.

Constructors

Deque()

Initializes a new instance of the Deque<T> class with the default initial capacity and auto-grow enabled.

public Deque()

Deque(IEnumerable<T>)

Initializes a new instance of the Deque<T> class containing elements copied from collection, sized to fit them, with auto-grow enabled.

public Deque(IEnumerable<T> collection)

Parameters

collection IEnumerable<T>

The collection from which elements are copied. Must not be null.

Exceptions

ArgumentNullException

collection is null.

Deque(IEnumerable<T>, int)

Initializes a new instance of the Deque<T> class containing elements copied from collection, with the specified capacity. Auto-grow is enabled.

public Deque(IEnumerable<T> collection, int capacity)

Parameters

collection IEnumerable<T>

The collection from which elements are copied. Must not be null.

capacity int

The initial backing-array capacity. Must be greater than zero, and at least collection.Count when auto-grow is disabled.

Exceptions

ArgumentNullException

collection is null.

ArgumentOutOfRangeException

capacity is less than 1.

Deque(IEnumerable<T>, int, bool)

Initializes a new instance of the Deque<T> class containing elements copied from collection, with the specified capacity and growth policy.

public Deque(IEnumerable<T> collection, int capacity, bool allowGrow)

Parameters

collection IEnumerable<T>

The collection from which elements are copied. Must not be null.

capacity int

The initial backing-array capacity. Must be greater than zero, and at least collection.Count when allowGrow is false.

allowGrow bool

true to allow the deque to expand its backing array when full; false for fixed-capacity behavior.

Exceptions

ArgumentNullException

collection is null.

ArgumentOutOfRangeException

capacity is less than 1.

InvalidOperationException

allowGrow is false and collection contains more elements than capacity.

Deque(int)

Initializes a new instance of the Deque<T> class with the specified initial capacity and auto-grow enabled.

public Deque(int capacity)

Parameters

capacity int

The initial capacity (or capacity hint when AllowGrow is true). Must be greater than zero.

Exceptions

ArgumentOutOfRangeException

capacity is less than 1.

Deque(int, bool)

Initializes a new instance of the Deque<T> class with the specified capacity and growth policy.

public Deque(int capacity, bool allowGrow)

Parameters

capacity int

The initial backing-array capacity. Must be greater than zero.

allowGrow bool

true to allow the deque to expand its backing array when full; false to throw InvalidOperationException from AddFirst(T) and AddLast(T) (and return false from their Try* variants) when full.

Exceptions

ArgumentOutOfRangeException

capacity is less than 1.

Properties

AllowGrow

Gets or sets a value indicating whether the deque expands its backing array when an add operation would overflow the current capacity.

public bool AllowGrow { get; set; }

Property Value

bool

true to grow on demand; false to apply OverflowPolicy once full - by default rejecting the add (throw from AddFirst(T) and AddLast(T), false from their Try* variants).

Remarks

This property may be toggled at runtime to switch the deque between fixed and growable modes. Switching from true to false does not shrink the existing backing array; call TrimExcess() if a smaller footprint is desired.

While this property is true, growth always wins and OverflowPolicy is never consulted - no element is evicted regardless of the configured policy.

OverflowPolicy

Gets or sets the policy applied when an add operation targets a full, fixed-capacity deque.

public DequeOverflowPolicy OverflowPolicy { get; set; }

Property Value

DequeOverflowPolicy

One of the DequeOverflowPolicy values. The default is Reject, which preserves the historical throw / return-false behavior.

Remarks

The policy is consulted only when AllowGrow is false and the deque is full. When AllowGrow is true the backing array grows instead - growth always wins, rendering the policy irrelevant on a growable deque.

Under EvictOpposite, AddFirst(T) discards the tail element and AddLast(T) discards the head element before storing the new item, keeping Count at Capacity - the Python deque(maxlen=N) semantics. Each eviction raises ItemEvicting beforehand and ItemEvicted afterwards.

Exceptions

ArgumentOutOfRangeException

The assigned value is not a defined DequeOverflowPolicy member.

Methods

AddFirst(T)

Adds item to the head of the deque.

public void AddFirst(T item)

Parameters

item T

The element to add. May be null for reference types.

Remarks

On a full, fixed-capacity deque with OverflowPolicy set to EvictOpposite, the tail element is silently discarded (raising ItemEvicting and ItemEvicted) and the new item is stored at the head, leaving Count unchanged.

Exceptions

InvalidOperationException

AllowGrow is false, OverflowPolicy is Reject, and the deque is already at capacity.

AddLast(T)

Adds item to the tail of the deque.

public void AddLast(T item)

Parameters

item T

The element to add. May be null for reference types.

Remarks

On a full, fixed-capacity deque with OverflowPolicy set to EvictOpposite, the head element is silently discarded (raising ItemEvicting and ItemEvicted) and the new item is stored at the tail, leaving Count unchanged.

Exceptions

InvalidOperationException

AllowGrow is false, OverflowPolicy is Reject, and the deque is already at capacity.

EnsureCapacity(int)

Ensures that the deque can hold at least capacity elements without further growth, expanding the backing array if necessary. Available regardless of AllowGrow.

public int EnsureCapacity(int capacity)

Parameters

capacity int

The minimum capacity required. Must be non-negative.

Returns

int

The new capacity of the backing array (which may exceed capacity).

Remarks

This method ignores AllowGrow - it is the explicit pre-grow hatch even on fixed-capacity deques. Use it to reserve space ahead of a known burst of inserts.

Exceptions

ArgumentOutOfRangeException

capacity is negative.

InvalidOperationException

capacity exceeds MaxLength and therefore cannot be satisfied.

PeekFirst()

Returns the head element without removing it.

public T PeekFirst()

Returns

T

The current head element.

Exceptions

InvalidOperationException

The deque is empty.

PeekLast()

Returns the tail element without removing it.

public T PeekLast()

Returns

T

The current tail element.

Exceptions

InvalidOperationException

The deque is empty.

RemoveFirst()

Removes and returns the head element.

public T RemoveFirst()

Returns

T

The element that was at the head.

Exceptions

InvalidOperationException

The deque is empty.

RemoveLast()

Removes and returns the tail element.

public T RemoveLast()

Returns

T

The element that was at the tail.

Exceptions

InvalidOperationException

The deque is empty.

TryAddFirst(T)

Attempts to add item to the head of the deque without throwing.

public bool TryAddFirst(T item)

Parameters

item T

The element to add. May be null for reference types.

Returns

bool

true if the item was added (including after growing or evicting the tail element); false if the deque was fixed-capacity, full, and OverflowPolicy is Reject.

Remarks

Returns true after auto-growing when AllowGrow is true, and after evicting the tail element when OverflowPolicy is EvictOpposite on a full, fixed-capacity deque. Returns false without modifying state only when the deque is full, AllowGrow is false, and OverflowPolicy is Reject.

TryAddLast(T)

Attempts to add item to the tail of the deque without throwing.

public bool TryAddLast(T item)

Parameters

item T

The element to add. May be null for reference types.

Returns

bool

true if the item was added (including after growing or evicting the head element); false if the deque was fixed-capacity, full, and OverflowPolicy is Reject.

Remarks

Returns true after auto-growing when AllowGrow is true, and after evicting the head element when OverflowPolicy is EvictOpposite on a full, fixed-capacity deque. Returns false without modifying state only when the deque is full, AllowGrow is false, and OverflowPolicy is Reject.

TryPeekFirst(out T)

Attempts to read the head element without throwing when empty.

public bool TryPeekFirst(out T item)

Parameters

item T

When this method returns, contains the head element if available.

Returns

bool

true if the head was read; otherwise false.

TryPeekLast(out T)

Attempts to read the tail element without throwing when empty.

public bool TryPeekLast(out T item)

Parameters

item T

When this method returns, contains the tail element if available.

Returns

bool

true if the tail was read; otherwise false.

TryRemoveFirst(out T)

Attempts to remove and return the head element without throwing when empty.

public bool TryRemoveFirst(out T item)

Parameters

item T

When this method returns, contains the removed element if successful.

Returns

bool

true if an element was removed; otherwise false.

TryRemoveLast(out T)

Attempts to remove and return the tail element without throwing when empty.

public bool TryRemoveLast(out T item)

Parameters

item T

When this method returns, contains the removed element if successful.

Returns

bool

true if an element was removed; otherwise false.

Events

ItemEvicted

Occurs immediately after an item has been evicted from the opposite end of the Deque<T> to make room for a new element.

public event Action<T>? ItemEvicted

Event Type

Action<T>

Remarks

This event is raised only when the deque is full, AllowGrow is false, and OverflowPolicy is EvictOpposite.

Important: Exceptions thrown by event handlers are not caught and will propagate to the caller of AddFirst(T), AddLast(T), TryAddFirst(T), or TryAddLast(T). Consumers should ensure event handlers are exception-safe.

ItemEvicting

Occurs immediately before an item is evicted from the opposite end of the Deque<T> to make room for a new element.

public event Action<T>? ItemEvicting

Event Type

Action<T>

Remarks

This event is raised only when the deque is full, AllowGrow is false, and OverflowPolicy is EvictOpposite.

Important: Any exception thrown from a handler vetoes the eviction in place - the opposite-end element is not removed, the new element is not stored, the count, head, and tail indices are unchanged, and the exception propagates to the caller of AddFirst(T), AddLast(T), TryAddFirst(T), or TryAddLast(T). Event handlers should therefore avoid throwing unless the veto is intentional.

Applies to

Product	Versions
.NET	8, 10