Stacks study guide

A reliable tracing method

When applying a sequence of stack operations, write the current contents after each operation, keeping the top clearly identified. For example, begin with an empty stack. After push(4), the stack contains [4], with 4 at the top. After push(9), it contains [4, 9], with 9 at the top. A peek returns 9 and leaves [4, 9] unchanged. A pop returns 9 and changes the stack to [4]. This demonstrates the essential distinction: peek reads the top value without removing it, while pop removes the top value.

Applying safety tests

A test for an empty stack should be considered before an operation that requires a top element, especially pop. If the test reports that the stack is empty, there is no value for pop to remove. A test for a full stack should be considered before push when the stack can reach a full condition. If the test reports that it is full, the attempted addition should not be treated as a successful push. The tests therefore help an algorithm choose whether an operation can be applied safely.

Exam reasoning

For a trace question, identify the top after every change rather than relying on the original order. State both the returned value and the resulting stack when explaining pop. For peek or top, state the returned value and explicitly say that the stack is unchanged. If asked to compare operations, explain the effect on the stack, not just the name of the operation. If asked to describe a sequence, show the intermediate state so that each later operation is based on the correct top element.

Self-check

After writing an answer, check these points: Have all pushed values been placed at the top? Has every popped value been removed? Has a peek result been recorded without changing the stack? Have empty and full tests been associated with the correct possible problem? Can you identify the top element at each stage? A correct trace should make the returned values and the final stack follow directly from the operations shown.