The Stack ADT: Push, Pop, and the Errors
Chapter Thirty-One
Syllabus topic Module 1, "Stacks: Stack ADT for Stack"
Pages 93 to 95 of 411
In one line
The stack ADT is push, pop, peek, is_empty and size, with two error conditions that are part of the specification and not an implementation detail.
The ADT
A Stack holds a sequence of items and permits access at one end only, called the top.
| Operation | Needs | Returns | Does | When it cannot |
|---|---|---|---|---|
Stack() | nothing | an empty stack | creates it | never fails |
push(item) | an item | nothing | puts it on the top | overflow if the stack is full |
pop() | nothing | an item | removes and returns the top | underflow if the stack is empty |
peek() | nothing | an item | returns the top, leaves it | error if the stack is empty |
is_empty() | nothing | true or false | is there nothing in it | never fails |
size() | nothing | a number | how many items | never fails |
That table is the answer to "write the ADT for a stack". Nothing in it mentions an array or a linked list, which is the point of chapter 7.
Underflow and overflow
These two words are examined, so they are worth being exact about.
Underflow is popping or peeking an empty stack. There is no top, so there is nothing to return. It can happen on any implementation, because emptiness is a property of the stack and not of its storage.
Overflow is pushing onto a full stack. It can happen only when the stack has a fixed capacity, which is the array implementation. A linked stack has no maximum and cannot overflow until the machine itself runs out of memory.
So the honest statement, which is what an examiner wants: underflow applies to every stack; overflow applies to a stack of fixed size.
Why they are errors and not quiet answers
The lazy implementation returns a special value, usually None or -1, instead of raising an error. It is worth seeing why that is a defect rather than a style choice.
class QuietStack:
"""Returns None on underflow. Looks harmless."""
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item)
def pop(self):
if not self._items:
return None
return self._items.pop()
class LoudStack:
"""Raises on underflow, as the ADT says."""
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item)
def pop(self):
if not self._items:
raise IndexError("pop from an empty stack: underflow")
return self._items.pop()
quiet = QuietStack()
quiet.push("a")
quiet.push(None) # a legitimate item that happens to be None
print("quiet stack, popping three times from a stack of two:")
for _ in range(3):
print(" got", repr(quiet.pop()))
print(" which of those was underflow? There is no way to tell.")
print()
loud = LoudStack()
loud.push("a")
print("loud stack:")
print(" got", repr(loud.pop()))
try:
loud.pop()
except IndexError as e:
print(" underflow reported:", e)quiet stack, popping three times from a stack of two:
got None
got 'a'
got None
which of those was underflow? There is no way to tell.
loud stack:
got 'a'
underflow reported: pop from an empty stack: underflowThe Stack ADT: Push, Pop, and the Errors
Two of those three None values mean different things: one is a real item that was pushed, one is the stack saying it is empty. The caller cannot distinguish them, so the error is carried forward into whatever uses the value, and it surfaces somewhere else entirely.
That is the same argument as chapter 9's, and it is why the ADT specifies the error rather than leaving it to the implementer.
A note on what pop returns
There are two conventions and both appear in textbooks:
Pop removes and returns the top. One operation. This is what this book uses and what most languages do.
Pop removes; top or peek returns. Two operations, so removing without looking is possible. C++'s std::stack works this way.
An examination answer may use either, as long as it is consistent and says which. What is wrong is a pop that returns the item in the specification and does not in the code.
The ADT in the form the examination wants
If the question says "write the stack ADT", the expected answer is roughly:
Stack: a collection of items with access at one end, the top.
push(item) : add item to the top. Overflow if full.
pop() : remove and return the top item. Underflow if empty.
peek() : return the top item without removing it. Error if empty.
is_empty() : true when the stack holds nothing.
size() : the number of items held.
All operations are O(1).
Adding the cost line is worth a mark and almost nobody writes it.
Quick revision
- The stack ADT: push, pop, peek, is_empty, size. All O(1).
- It names no array and no linked list.
- Underflow: popping or peeking an empty stack. Applies to every implementation.
- Overflow: pushing onto a full stack. Applies only to a fixed capacity stack, so to the array version
and not the linked one.
- Errors are part of the specification. Returning None instead makes a real None item and an empty stack
indistinguishable to the caller.
- Two conventions for pop exist; either is acceptable if stated and applied consistently.
Test yourself
1. Write the stack ADT. A collection with access at one end. push(item) adds at the top, overflow if full; pop() removes and returns the top, underflow if empty; peek() returns the top without removing it, error if empty; is_empty(); size(). All operations are O(1).
2. Define underflow and overflow, and say which implementations each applies to. Underflow is popping or peeking an empty stack and applies to every implementation. Overflow is pushing onto a full stack and applies only to a fixed capacity stack, which is the array version.
The Stack ADT: Push, Pop, and the Errors
3. Why is returning None on underflow a defect? Because None may be a legitimate item. The caller cannot tell a real value from the stack reporting emptiness, so the mistake travels to somewhere unrelated before it causes a visible failure.
4. Can a linked stack overflow? Not in the sense the ADT means. It has no fixed capacity, so it fails only when the machine runs out of memory altogether.
5. Give the two conventions for pop, and what makes an answer wrong. Pop removes and returns the top; or pop removes while a separate top or peek returns it. An answer is wrong when the specification and the code disagree, not when it picks one convention.
6. What line does almost nobody write in this answer, and why is it worth a mark? That every operation is O(1). It is part of what the ADT promises and it is what makes the stack worth choosing.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.