StacksQueues/Java

Notes

Stacks and Queues in Java are implemented as part of the Collections library. Also implemented are Deques and priority queues.

Goodrich Java Chapter 6

Chapter 6 of Goodrich covers stacks and queues. These data structures can be implemented using array-based or link-based data structures. Thus, when covering data structures it's useful to start by covering array-based data structures that are dynamic, and their big-O cost of operations.

Queue - singly-linked list implementation - single head pointer - allows us to:

• insert/remove at the head with O(1)
• insert/remove at the tail with O(n)

Removing is O(n) because in a singly-linked list, we need the thing that links to tail.

Implementations

Stacks and queues can be implemented using various implementations:

• fixed/variable size
• contiguous/linked memory structure (array list vs linked list)
• singly/circular/doubly linked lists
• size of lists, size of objects and pointers

measurement/profiling of Java code for memory and performance, timing, etc.

• inputs X, outputs Y, with timing/profiling.

ArrayStack

implementation of a stack using a fixed or variable size array.