Class ArrayListQueue<T>

A IQueue<T> implementation based on an array list of items.

Inheritance
System.Object
ArrayBasedDataStructure<T>
ArrayListQueue<T>
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Queues
Assembly: MoreStructures.dll
Syntax
public class ArrayListQueue<T> : ArrayBasedDataStructure<T>, IQueue<T>
Type Parameters
Name Description
T

Remarks

ADVANTAGES AND DISADVANTAGES
- The advantages an disadvantages of using an array list over a linked list-based implementation are the same as the ones described in LinkedListStack<T>.

Constructors

| Improve this Doc View Source

ArrayListQueue(Int32, Double)

Declaration
public ArrayListQueue(int capacity = 16, double increasingFactor = 2)
Parameters
Type Name Description
System.Int32 capacity
System.Double increasingFactor

Properties

| Improve this Doc View Source

Count

Declaration
public int Count { get; }
Property Value
Type Description
System.Int32
Remarks

Stored and updated in constant time at each Enqueue(T) and Dequeue().
Time and Space Complexity are O(1).

Methods

| Improve this Doc View Source

Dequeue()

Declaration
public T Dequeue()
Returns
Type Description
T
Remarks

First, it retrieves the least recent item set into the underlying array list (whose index is internally stored).
Then, it reset the value at such index and decreases the Count by 1.
Then, if the new Count is smaller than the current capacity by more than twice the IncreasingFactor compoundly (i.e. capacity * increasingFactor^2), the underlying array list is resized to have a new capacity equal to the old capacity times the increasing factor.
Finally, it returns the retrieved item as result.
Raises an if the array list is empty.
Time and Space Complexity are O(1).

| Improve this Doc View Source

Enqueue(T)

Declaration
public void Enqueue(T item)
Parameters
Type Name Description
T item
Remarks

If there is available room in the underlying array, the new item is stored in the first available location (applying circular arithmetic to indexes) and the Count is increased by 1.
Otherwise the underlying array is resized by the IncreasingFactor, to accomodate the new item.
Time and Space Complexity are O(1) if Count before insertion is strictly smaller than the current capacity.
Time and Space Complexity are O(n) if Count before insertion is equal to the current capacity.
If the IncreasingFactor is set to a sensible value (e.g. 2.0), the amortized cost over n insertions becomes O(1).

| Improve this Doc View Source

Peek()

Declaration
public T Peek()
Returns
Type Description
T
Remarks

Checks and returns the item of the underlying array list at the first index set (which is internally stored), if it exists.
Throws a if the underlying array is empty.
Time and Space Complexity are O(1).

| Improve this Doc View Source

ResizeItems(Double)

Declaration
protected override void ResizeItems(double factor)
Parameters
Type Name Description
System.Double factor
Overrides
MoreStructures.Stacks.ArrayBasedDataStructure<T>.ResizeItems(System.Double)
Remarks

After resizing, it copies items appropriately to restore circular arithmetic of indexes which is now based on a different modulo.
If the size of the array has been increased, copy will happen from the front of the backing array to the front of its second half (introduced by the resizing).
If the size of the array has been reduced, copy will simply scan the entire old array, remapping indexes into the new array.

Implements

Extension Methods