In an array-backed stack, what changes in push, pop and the empty check if `top` means the next free slot?
answer
- write the invariant before the operations
- what does top mean when empty
- one convention needs a negative sentinel
- the other makes top equal the count
- check push, pop and empty against one rule
basics
~20 sTwo conventions exist: top indexes the last element (empty is top == -1, push increments then writes), or top indexes the next free slot (empty is top == 0, push writes then increments). Pick one and check every operation against it.
solid answer
~40 sThe bookkeeping is a single invariant, and every operation must agree with it. If `top` indexes the last element, empty is `top == -1`, `push` increments then writes `a[top]`, `pop` reads `a[top]` then decrements, size is `top + 1`, and full is `top == capacity - 1`. If `top` is the next free slot — the count convention — empty is `top == 0`, `push` writes then increments, `pop` decrements then reads, size is just `top`, and full is `top == capacity`. Both are correct; mixing them is the classic defect, and it shows up as an off-by-one that bites only at the boundaries: pushing into an empty stack, popping the last element, filling to capacity. In review I want the invariant in one comment and every operation read against that sentence.
code
pseudocode · 18 lines// invariant: slots 0..top hold live elements; top == -1 means empty
top = -1
push(x):
if top == capacity - 1
signal Overflow
top = top + 1
a[top] = x
pop():
if top == -1
signal Underflow
x = a[top]
top = top - 1
return x
empty(): return top == -1
size(): return top + 1go deeper
Be able to write one of the two conventions correctly and say out loud what top means when the stack is empty. Knowing that the empty resting value differs between conventions is most of the answer at this level.
Explain both conventions end to end — empty check, size, full check, and the order of write and increment in push — and name the boundary cases where mixing them breaks: push into empty, pop the last element, fill to capacity.
Show a review method rather than a trace: locate the initializer, state the invariant, and read every operation against it. Expect to say which boundary tests you require before approving a fixed-capacity buffer.
Own the convention as a codebase-wide decision. Argue for the one that fails loudly and needs no sentinel, and treat an unstated invariant on a shared structure as the defect, separate from whether today's arithmetic happens to be right.
## The invariant is the whole design An array-backed stack is two things: a block of slots and one integer that says where the live region ends. Everything else — push, pop, peek, the empty check, the size, the full check — is derived from what that integer means. Choose the meaning first, write it as one sentence, and the five operations follow mechanically. Skip that step and you get an off-by-one that passes every mid-range test and fails at the two boundaries nobody wrote a case for. ## Convention A — `top` is the index of the last element The invariant: *slots 0 through `top` hold live elements; `top == -1` means empty.* - empty check: `top == -1` - size: `top + 1` - full: `top == capacity - 1` - push: increment `top`, then write `a[top]` - pop: read `a[top]`, then decrement `top` - peek: read `a[top]` This reads naturally — `a[top]` really is the top element — at the cost of a negative sentinel for the empty state. That sentinel is where the trouble starts: an unsigned counter cannot hold it, and a size computed as `top` instead of `top + 1` is off by one everywhere. ## Convention B — `top` is the next free slot (the count convention) The invariant: *slots 0 through `top - 1` hold live elements; `top` is where the next push lands.* - empty check: `top == 0` - size: `top` - full: `top == capacity` - push: write `a[top]`, then increment `top` - pop: decrement `top`, then read `a[top]` - peek: read `a[top - 1]` Here `top` is literally the element count, the empty state needs no sentinel, and the value is never negative. The cost is that reading the top element requires the `- 1`, which is exactly where a reviewer should look hardest. ## What the off-by-one looks like in a diff The bug is almost never a whole wrong operation. It is one operation written under the other convention, dropped into a file that otherwise follows one rule. Three shapes recur: 1. **push increments in the wrong order.** Under convention B, writing `a[++top]` skips slot 0 forever and reports a size one larger than reality; the first pushed element is never readable again. 2. **the empty check uses the wrong resting value.** `top == 0` under convention A means "one element, sitting in slot 0" — so the check reports empty when the stack holds exactly one item, and the last element silently disappears. 3. **the full check is off by one at capacity.** Under convention A, `top == capacity` never becomes true before a write past the end; the guard has to be `top == capacity - 1`. All three survive a test that pushes three elements and pops two. They fail only at the boundaries: push into empty, pop the last one, fill exactly to capacity, then push once more. Those four cases are the review checklist as much as the test list. ## Reading it in review When you are the reviewer looking at a fixed-capacity stack that buffers device readings, do not trace the arithmetic operation by operation — you will convince yourself of whichever convention you started reading with. Instead: find the initialization of `top`, infer the invariant from it, and then read each operation asking one question — "is this consistent with that sentence?" An initializer of `-1` demands convention A everywhere; an initializer of `0` demands convention B everywhere. A file that initializes to `0` and then peeks at `a[top]` has already told you the answer. ## Which one to pick For new code, the count convention (B) is the easier one to keep correct: no negative sentinel, size is free, the empty and full checks are the two natural extremes of a count, and the whole thing survives being stored in an unsigned counter. Convention A pays for its readable `a[top]` with a special value that has to be threaded through every check. Either is fine as long as the choice is stated once, in the code, next to the field it constrains — and as long as the boundary cases have tests rather than confidence.
- Which convention would you choose for new code, and why?The next-free-slot convention. `top` becomes the element count, so the size is free, the empty check is `top == 0` with no negative sentinel to thread through, the full check is `top == capacity`, and the value is never negative — which matters if it is stored in an unsigned counter. The price is a `- 1` when reading the top element, and that single expression is easy to spot in review.
- How do you catch a top-pointer off-by-one in review rather than in production?Find the initializer, infer the invariant, then read every operation against that one sentence instead of tracing arithmetic. Then check the boundary tests exist: push into an empty stack, pop the last element, fill exactly to capacity, and push once more. Mid-range sequences pass under both conventions, so they prove nothing — only the boundaries separate a correct implementation from a broken one.
- Does the empty check belong inside pop or as a separate query the caller uses?Both, and they answer different needs. The guard inside `pop` protects the invariant unconditionally, so a caller mistake becomes a reported failure rather than a read of an out-of-range or stale slot. The separate query lets a caller decide *before* committing to a removal — for example, to stop a drain loop. Offering only the query, and trusting callers, is how underflow reaches production.
It is the difference between a bookmark on the last page you read and a bookmark on the next page to read. Both work; a reader who forgets which one they chose loses or repeats a page every time.
saying these in an interview costs you the question
- Says the convention does not matter, just pick one
- Uses top == 0 as the empty check under both conventions
- Writes push as increment-then-write under the count convention
- Guards overflow with top == capacity when top indexes the last element
- Tests only mid-range sequences, never the boundaries
- Computes size as top under the count-minus-one convention