Stacks revision notes

What a stack operation does

A stack supports access through its top element. The operations in the specification are:

• push: adds a value to the top of the stack.
• pop: removes the top element from the stack. The removed value may then be used by the algorithm.
• peek or top: returns the value of the top element without removing it.
• test for empty stack: checks whether the stack currently contains no elements.
• test for stack full: checks whether the stack has reached the condition in which it cannot accept another element.

Applying the operations

Suppose the current stack, shown from bottom to top, is [A, B]. Applying push(C) gives [A, B, C]. Applying peek returns C, but the stack remains [A, B, C]. Applying pop removes and returns C, leaving [A, B].

Before using pop, an algorithm should test whether the stack is empty. Popping from an empty stack is an invalid application of the operation because there is no top element to remove. Before using push, an algorithm can test whether the stack is full. If the stack is full, the algorithm should not attempt to add another value.

Common errors

Do not describe peek as removing the top value: it only returns that value. Do not confuse pop with inspecting the top: pop changes the stack by removing its top element. When tracing operations, update the stack after every push and pop, but not after peek. Also distinguish the two tests: empty concerns whether there are no elements, whereas full concerns whether another element can be added.