Two Stacks, Side by Side

We now have two implementations of the Stack contract, so we can put the costs side by side, as we did with the two lists in Chapter 7:

Operation	`ArrayStack`	`LinkedStack`
`push`	$O (1)$ amortized	$O (1)$
`pop`	$O (1)$	$O (1)$
`top`	$O (1)$	$O (1)$
`isEmpty`	$O (1)$	$O (1)$

What about space complexity? Asymptotically, both have the same space complexity. However, the memory usage differs. ArrayStack stores its items in one contiguous block. The capacity is usually larger than the count, and our implementation never shrinks the array. LinkedStack allocates exactly one node per item. Each node uses extra memory for its next reference, and the nodes are not stored next to each other in memory.

Why the trade-offs are small? The reason is the small interface. An array can add and remove at its end in $O (1)$ ; a linked list can add and remove at its head in $O (1)$ . The List ADT requires access by index and removal at any position, so each structure has some operations that cost $O (n)$ . The Stack ADT requires only operations on the top item, and each implementation puts the top at the end it can update in $O (1)$ .

This is a second benefit of restricting access. The first benefit was protecting the order of items. This one is efficiency. An interface this small can be implemented cheaply on either structure.

So which one should you use? Either one works. Remember a client should program to the interface, declaring Stack<T> without caring which class is behind it.