Stacks and queues

Spring collections implement three types of collections that are foundational to computer science – a stack (LIFO), a queue (FIFO), and a double-ended queue (deque). Although both queues (and sometimes the stack) are frequently implemented with a linked list, Spring collections implement them with dynamic arrays. This approach is much faster as it doesn’t require frequent allocations of small memory blocks.

Tip

Spring collections include a linked list implementation, ILinkedList<T>, where each node is represented by a TLinkedListNode<T> object, but it is better to ignore it. The implementation in Spring is perfectly fine but this approach – allocating many small blocks of memory – doesn’t work well on modern CPU architectures. Allocated memory is usually not sequential, which leads to poor cache performance when walking over such structures. Use other collections if at all possible.

IStack<T>

A stack...