Stacks and Queues: Implementation Trade-offs

Stacks and Queues: Implementation Notes

Linked-List Implementation

• Performance: Constant time (O(1)) for push and pop operations.
• Drawback: Can be slower than array implementations due to the overhead of node creation and pointer manipulation.

Array Implementation

• Challenge: Requires a fixed capacity, which can lead to issues.
  • Loitering: Holding references to objects that are no longer needed, preventing garbage collection.
• Resizing Arrays: A common solution to handle dynamic capacity.
  • Growth: When the array is full, create a new array (typically twice the size) and copy all items. This is an example of amortized analysis, where the cost is averaged over many operations.
  • Shrinking (Thrashing): To avoid excessive resizing when an array fluctuates around a capacity boundary, a common strategy is to shrink the array only when it is, for example, 1/4 full. This prevents a rapid sequence of expensive grow-and-shrink operations.

Java-Specific Concepts

• Generics: Allow for type-safe data structures (e.g., Stack<String>).
• Iteration: Implementing the Iterable interface allows data structures to be used with Java’s for-each loop.