Example: stack

A stack interface can provide push, pop, peek and is_empty. Its rule is last-in, first-out. A client should obtain the most recently pushed remaining value from pop, regardless of whether the stack uses an array or linked nodes.

Interface contract

1. State the supported values and operations.
2. Specify success and failure results, such as empty-stack removal.
3. State which operation changes the collection.
4. Hide representation details that the caller does not need.

Implementation

An array stack can keep an element array and a top index. A linked stack can keep a head pointer and allocate nodes. Both can satisfy the same abstract rule, but have different capacity, allocation and locality properties. An ADT is not just a C struct declaration: behaviour is part of the definition.

Benefits

The client can use operations without rewriting representation logic. Testing can verify observable behaviour. An implementation can be replaced while keeping a compatible contract. In C, headers and carefully designed functions support this separation, although C does not automatically enforce every abstraction boundary.

Complexity

An ADT description should not be confused with an unconditional performance promise. The chosen implementation determines operation costs. Document those costs separately; for example, the array and linked stack versions shown later provide O(1) push/pop excluding allocator internals.