Stack & Amortized Analysis

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

• Explain and trace the core operations of Stack (push, pop, top, empty).
• Describe the difference between top and pop.
• Implement the core operations of Stack efficiently (array-based and linked-based).
• Implement an array-based Stack that dynamically grows as more space is needed.
• Determine the cost of dynamically resizing an array-based implementation of Stack.
• Describe what amortized analysis is.
• Explain the difference between amortized constant time and actual constant time.
• Elaborate on the importance of array growth factor to maintain amortized constant time push operation.

Starter code for this chapter