Stack Operations and Implementation

Push adds an item to the top. Pop removes and returns the top item; peek returns it without removing it. A stack can support undo history, nested expression evaluation and routine calls because the latest unfinished activity is handled first.

An empty-stack test prevents removal when no item exists. A bounded implementation also tests for full storage before push. Stack underflow is an invalid removal from empty; overflow in this model means adding beyond capacity. These conditions should be handled before corrupting the state.

For a fixed array, let size be the next free index and the number of logical items. Initially size=0. Push writes at array[size] and then increments size. Pop first decrements size and then returns array[size]. Peek reads array[size-1] while leaving size unchanged.

Some descriptions instead use top as the index of the current top, initially -1. Both conventions can work, but combining their updates causes off-by-one errors. Removing an item can leave its old value in physical storage; the logical boundary determines whether it is still in the stack.

In the basic bounded-array model, each push, pop or peek takes constant time once validity is checked. A resizable array may occasionally perform a more expensive allocation and copy, while linked representations require additional references. State the implementation before making a cost claim.

Two stacks can implement browser-like back and forward histories, but the behaviour of a real product may include extra rules. For an examination trace, use the operations and starting contents provided. A stack’s order is about insertion history, not numerical sorting.

stack = []
stack.append("A")
stack.append("B")
print(stack[-1])
print(stack.pop())
print(stack)

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.