The Stack

This chapter covers the Stack ADT, a collection where a client can work only with the most recently added item. We implement it twice, as ArrayStack and LinkedStack, and compare the two.

After reading this chapter, you should be able to:

• Describe the Stack ADT: the push, pop, top, and isEmpty operations, the last-in, first-out rule, and the documented exception behavior
• Implement and trace ArrayStack, with the end of the array as the top, and LinkedStack, with the head of the list as the top
• Compare the two implementations, and explain why a stack’s limited interface lets both run every operation in $O(1)$, with push on ArrayStack amortized
• Recognize last-in, first-out behavior in a problem as the cue to use a stack

You can download the accompanying code for this chapter: starter and solution.

Sections

1. Implementing Undo
2. The Stack ADT
3. Stack ADT Specification
4. Using an Array to Implement a Stack
5. The ArrayStack Class
6. Implementing isEmpty, top, and pop
7. Implementing push
8. Tracing the ArrayStack
9. Using a Linked List to Implement a Stack
10. The LinkedStack Class
11. Implementing pop, top, and push
12. Tracing the LinkedStack
13. Two Stacks, Side by Side