loading...

Stacks

jjb profile image JB Updated on ・1 min read

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!

Discussion

pic
Editor guide