Class ArrayListStack<T>

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

Inheritance
System.Object
ArrayBasedDataStructure<T>
ArrayListStack<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.Stacks
Assembly: MoreStructures.dll
Syntax
public class ArrayListStack<T> : ArrayBasedDataStructure<T>, IStack<T>
Type Parameters
Name Description
T

Remarks

ADVANTAGES AND DISADVANTAGES
- Compared to an implementation based on a linked list, such as LinkedListStack<T>, it has a lower memory footprint and a lower cost of memory management, due to the fact that a single object made of a contiguous area in memory is used, to store all items.
- In particular, no need for per-item additional space is required, as it happens for "next" references and objects overhead in linked list-based solutions.
- On the flip side, the requirement for a potentially large contiguous chunk of memory in the heap may produce when trying to instantiate or resize stacks of large capacity, especially when the memory is heavily fragmented.
- Moreover, each insert which happens when the underlying array has been fully occupied requires work proportional to the current size of the stack, since the underlying array cannot be extended without instantiating a larger array and performing a full copy from the old to the new one.
- That means that insertion cost won't be O(1) all the time, but only in average, as amortized complexity over n operations (assuming that IncreasingFactor is left to its default value DefaultIncreasingFactor, or chosen sensibly).
- That can be a significant drawback in realtime systems where insertion cost has to be highly predictable and also very low.

Constructors

| Improve this Doc View Source

ArrayListStack(Int32, Double)

Declaration
public ArrayListStack(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 Push(T) and Pop().
Time and Space Complexity are O(1).

Methods

| 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 last index set (which is Count - 1), if it exists.
Throws a if the underlying array is empty.
Time and Space Complexity are O(1).

| Improve this Doc View Source

Pop()

Declaration
public T Pop()
Returns
Type Description
T
Remarks

First, it retrieves the last item set into the underlying array list (which is the one at index Count - 1).
Then, it reset the value of the last item 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

Push(T)

Declaration
public void Push(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 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).

Implements

Extension Methods