A Stack on an Array, With Peek
Chapter Thirty-Two
Syllabus topic Computer Science Practical 3, Module 2, "Implement push, pop, peek using arrays or linked lists"
Pages 96 to 98 of 411
In one line
An array stack keeps the items in a fixed block with an integer marking the top, so push writes at top + 1 and pop reads at top, both O(1).
The design
Two fields: the block of cells, and an integer top.
The usual convention, and the one to state in an answer: top is the index of the topmost item, and -1 means empty. An empty stack has no topmost item, so -1 is the value just below the first cell.
empty : top = -1
after push : top = top + 1, then cells[top] = item
after pop : item = cells[top], then top = top - 1
full : top = capacity - 1
The order inside push and pop is the mirror of each other, and getting it wrong by one is the classic error: incrementing after writing overwrites the item below.
Built and run
class ArrayStack:
"""A stack in a fixed block, with top as the index of the topmost item."""
def __init__(self, capacity):
self.capacity = capacity
self.cells = [None] * capacity
self.top = -1 # -1 means empty
def is_empty(self):
return self.top == -1
def is_full(self):
return self.top == self.capacity - 1
def size(self):
return self.top + 1
def push(self, item):
if self.is_full():
raise OverflowError("push onto a full stack: overflow (capacity %d)"
% self.capacity)
self.top += 1
self.cells[self.top] = item
def pop(self):
if self.is_empty():
raise IndexError("pop from an empty stack: underflow")
item = self.cells[self.top]
self.cells[self.top] = None # so a popped item is not kept alive
self.top -= 1
return item
def peek(self):
if self.is_empty():
raise IndexError("peek at an empty stack: underflow")
return self.cells[self.top]
def snapshot(self):
return self.cells[:self.top + 1]
s = ArrayStack(4)
print("new stack: empty =", s.is_empty(), "| size =", s.size(), "| top =", s.top)
for item in ("A", "B", "C"):
s.push(item)
print("push %s -> %-16s top = %d, size = %d"
% (item, str(s.snapshot()), s.top, s.size()))
print()
print("peek ->", s.peek(), "| size is still", s.size())
print("pop ->", s.pop(), "| now", s.snapshot())
print("pop ->", s.pop(), "| now", s.snapshot())
print()
s.push("X")
s.push("Y")
s.push("Z")
print("filled to capacity:", s.snapshot(), "| full =", s.is_full())
try:
s.push("one too many")
except OverflowError as e:
print("overflow reported:", e)
print()
empty = ArrayStack(2)
for operation in ("pop", "peek"):
try:
getattr(empty, operation)()
except IndexError as e:
print("%-5s on an empty stack ->" % operation, e)new stack: empty = True | size = 0 | top = -1
push A -> ['A'] top = 0, size = 1
push B -> ['A', 'B'] top = 1, size = 2
push C -> ['A', 'B', 'C'] top = 2, size = 3
peek -> C | size is still 3
pop -> C | now ['A', 'B']
pop -> B | now ['A']
filled to capacity: ['A', 'X', 'Y', 'Z'] | full = True
overflow reported: push onto a full stack: overflow (capacity 4)
pop on an empty stack -> pop from an empty stack: underflow
peek on an empty stack -> peek at an empty stack: underflowA Stack on an Array, With Peek
Both error conditions of chapter 31 are real here: underflow on the empty stack, and overflow, which the linked version of the next chapter cannot produce.
Two details worth marks
peek does not change top. It is the one operation that reads without moving, and writing self.top -= 1 into it by habit is a common slip. The run above checks it: size is still 3 after peek.
The popped cell is cleared. self.cells[self.top] = None is not required for correctness, because top already says that cell is not in use. It is there so the popped object is not kept alive by a reference nobody can reach. In C the equivalent is that the cell still holds a stale pointer, and reading it is a real bug.
The capacity problem
The array stack's one weakness is the number you have to choose at the start.
Too small and it overflows on valid input. Too large and memory sits reserved and unused. And there is often no good way to know: the depth of a stack used for bracket matching depends on the input.
Two answers exist.
Grow it, as Python's list does: when full, allocate a bigger block, copy, continue. This makes push amortised O(1) rather than O(1), by the argument of chapter 12, and it means overflow effectively disappears.
Use links, which is the next chapter, and have no capacity at all.
Quick revision
- Fields: a fixed block of cells, and
top, the index of the topmost item, with -1 meaning empty. - push: increment top, then write. pop: read, then decrement. The order is the mirror; reversing either
is an off-by-one that overwrites or re-reads.
- full is
top == capacity - 1; size istop + 1. - peek reads without changing top.
- Both error conditions are real here: underflow and overflow.
- Clear the popped cell so a dead item is not kept alive, and in C so a stale pointer is not left.
- The capacity must be chosen in advance, which is the weakness; growing the block or using links are
the two answers.
Test yourself
1. What does top hold, and what value means the stack is empty? The index of the topmost item. -1 means empty, because an empty stack has no topmost item.
2. Write push and pop in terms of top. push: check full, top = top + 1, then cells[top] = item. pop: check empty, item = cells[top], then top = top - 1.
A Stack on an Array, With Peek
3. What goes wrong if push writes before incrementing? It overwrites the item already at the top instead of adding above it, so the stack silently loses an item on every push.
4. Give the conditions for full and for size. Full is top == capacity - 1. Size is top + 1.
5. Which error can this implementation raise that a linked stack cannot, and why? Overflow, because the capacity is fixed at creation. A linked stack has no maximum until the machine runs out of memory.
6. Why clear the cell when popping, given that top already marks it unused? So the popped object is not kept alive by an unreachable reference; and in C, so a stale pointer is not left in the cell to be read by mistake.
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.