A stack is a special data structure where you only add, access, and remove elements from its top. A stack is also known as a last-in first-out (LIFO) structure.
As you learned in Phase 1, your computer uses a call-stack when it executes code. You probably blew the call stack more than a few times when you studied recursion.
Stacks are simple data structures, but they're powerful too. A simple infix (e.g. 3 + 4) expression parser can be produced using nothing but stacks, queues and the Shunting-yard algorithm, and executed using a stack-based reverse-polish notation calculator.
Most importantly for us, they're a classic example of a first-in-last-out (FIFO) data structure. FIFO and LIFO (last-in-first-out) are a useful part of your technical vocabulary as you reason about data and how it's processed.
Write and test a Stack class that conforms to the following interface:
Stack#new(): Instantiate a newStackStack#push(element): Add a new element to the top of the stackStack#pop: Remove and return the top element of the stackStack#top: Return (but do not remove) the top element of the stackStack#empty?: Answer whether or not the stack is empty
Do not use any Ruby data structures in your implementation. Instead, pick one of your own to use in your implementation:
- FixedArray
- ArrayList
- LinkedList
##Resources