COMP 271 002 F17 Lab 5 (Week 7)
Work in teams of two, optionally.
An understanding of the following concepts and techniques:
- ADT implementation perspective
- stack ADT
- dynamically allocated objects
- implementing stack as linked list
- algorithms based on the stack's LIFO policy
- interface-based testing
In this lab, you will have the opportunity to implement a generic stack as a linked list and use this implementation to solve a simple problem.
- Complete the TODO items in the
LinkedStackimplementation until the tests pass.
- Complete the main class
ReverseLines, which reads successive input lines until EOF and then prints themin reverse order, using a suitable stack instance.
- Answer the following questions:
- Why does
LinkedStacknot require an explicit constructor?
- What is the time and (extra) space complexity of each of the
LinkedStackmethods, as well as
- How else (not using
Node) could we have implemented
LinkedStackin such a way that it is still based on a linked list but the
asListmethod uses constant time and space?
- Is it better for
popto return the item or the stack itself? Briefly discuss the pros and cons of each design.
- Why does
- 8 submission via GitHub
- 16 completion of items marked TODO in
LinkedStackand tests passing
- 8 completion of
ReverseLinesand correct behavior
- 8 written part
- 6 responses to the questions above
- 2 grammar, style, formatting
40 points TOTAL