Practice question · Multiple choice
A stack ADT implemented with a fixed-size array can overflow when pushed too many times; the same ADT over a linked list cannot. Does that mean the array implementation is wrong?
Hints
- Ask what the ADT actually promised about capacity.
- Can an implementation be judged correct without knowing the specification?
Show the answer
D. No - it means the ADT's specification did not say.
Why
Correctness is relative to a specification, so the question cannot be answered until one is stated. Which is why capacity limits and error behaviour belong in the interface, 'push raises StackFull at capacity' is a promise callers can program against. The linked version pays for its unboundedness in pointers and cache behaviour, and a growable array is the usual compromise.
Practise Abstract Data Use
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Abstract Data Use
- A team replaces a stack's array implementation with a linked-node one. The published operations behave…
- A library documents a function's behaviour but not its complexity. Callers then write loops assuming it is…
- Order what happens when an object is created and then used.
- Because an ADT's interface says nothing about cost, two correct implementations of the same interface can…
- A stack ADT is being documented. Sort each statement by whether it belongs in the published interface or is…