Stacks

Resources

1. Stack overview
2. Stack implementation
3. Stack overview and implementation

Takeaways:

• Stacks are LIFO (Last In First Out) - similar to a stack of books. When you retrieve an element from a Stack, you get the element that was added most recently.
• The last element added to a Stack is called the "top" element. This makes sense if you think about the stacking books analogy - the book you add last will be at the top!
• Stacks have fast operations: adding (pushing), removing (popping), and retrieving the top/last element (peeking) are all O(1) (constant).
• Space is O(n).
• Stacks are commonly implemented with Arrays or Linked Lists. To keep my implementation simple, I went with a regular (versus dynamic) array - this means the consumer of the Stack class is required to provide a size on initialization.

Here's the finished implementation with test code:

As always, if you found any errors in this post please let me know!