Why start from ADT contracts
In data structures, implementation details are secondary to operation contracts. An ADT (Abstract Data Type) defines the legal operations, the state guarantees, and the error cases before we commit to arrays, linked lists, or any specific layout.
Stack ADT: operation semantics
Definition
Stack ADT core operations
For a stack :
push(x): insertxon top,pop(): remove and return top element,top(): return top element without removing,isEmpty(): return whether is empty.
LIFO is not a slogan. It is an invariant: if a is pushed before b, then b
must be popped before a unless removed by error handling.
Worked example
State trace for push/pop/top
Start with empty stack.
push(10)->[10]push(20)->[10,20](top is20)top()returns20, state unchangedpop()returns20, state becomes[10]
Queue ADT: operation semantics
Definition
Queue ADT core operations
For a queue :
enqueue(x): insertxat rear,dequeue(): remove and return front element,front(): inspect front without removal,isEmpty(): return whether is empty.
Queue invariant is FIFO: earlier inserted item exits earlier.
Worked example
State trace for enqueue/dequeue
Start with empty queue.
enqueue(3)->[3]enqueue(5)->[3,5]dequeue()returns3, queue becomes[5]front()returns5, state unchanged
Function-pointer dispatch in C
When implementing ADT operations in C, we often store function pointers in an operation table so code can switch behavior by structure type without rewriting call sites.
Theorem
Interface consistency via function pointers
If every implementation of an ADT exposes the same function-pointer signatures, client code can remain stable while underlying structures vary.
This is effectively manual polymorphism in C.
Read and try
Trace ADT operation semantics
The stepper shows operation-by-operation state transitions so ADT contracts can be checked directly.
Row operation: push(10)
stack: [10]
queue: []
Top now points to 10.
Common mistakes
Common mistake
Mixing stack and queue invariants
Using enqueue/dequeue names but applying LIFO behavior (or vice versa)
breaks ADT contracts even if code compiles.
Common mistake
Ignoring empty-structure preconditions
pop and dequeue on empty structures need explicit error policy (status code,
exception-like return, or sentinel with validity flag).
Quick checks
Quick check
After push(1), push(2), pop(), what remains in the stack?
Apply LIFO strictly.
Solution
Answer
Quick check
After enqueue(4), enqueue(7), dequeue(), which element is returned?
Apply FIFO strictly.
Solution
Answer
Exercises
Quick check
Design precondition/postcondition for stack pop().
Write one valid contract in words.
Solution
Guided solution
Quick check
Explain in one paragraph why an operation table of function pointers helps testing.
Focus on swapping implementations with unchanged client tests.
Solution