1.1 ADT operations: stack, queue, and function pointers

One interface, different representations

A stack can store its elements in an array or in linked nodes. After successful push(10) and push(20) calls, a client expects pop() to return 20 in either case. Array indices and node addresses are different, but the observable sequence is the same. If the client instead reads an internal count field or follows a node link, changing the representation can break that client even when the stack's behavior remains correct.

An abstract data type separates this observable behavior from the storage used to realize it. Preconditions specify when an operation is legal; postconditions specify its result and the state left behind. Failure behavior is also visible: a bounded stack that rejects a push and a growing stack that accepts it cannot be treated as identical unless the shared contract accounts for that difference.

Abstract state and failure atomicity

The abstract state is the mathematical value seen by a client, such as a finite sequence of stored elements. Array indices, capacities, and node addresses are not part of that value. A mutating operation should first validate its preconditions and obtain any required resource, then commit the representation change. If it reports overflow, underflow, or allocation failure, failure atomicity requires the old abstract state to remain observable. This rule prevents a failed insertion from changing the depth or length and prevents a failed removal from discarding an element before an error is reported.

One precise way to connect code with this abstract state is an abstraction function. It maps every valid concrete representation to exactly one abstract sequence. The representation invariant describes which concrete states are valid; the operation contract describes how the mapped sequence may change. These roles must remain separate. A client is entitled to the operation contract, but it neither sees nor repairs an internal invariant. Conversely, an implementation may reorganize storage while an operation is running, provided no intermediate form escapes and the final concrete state maps to the promised abstract result.

Failure atomicity can be designed as a short transaction. First inspect all logical preconditions without mutation. Next calculate any new capacity or link values and reject arithmetic overflow. Then acquire memory or other resources while the old representation is still intact. Finally publish the new pointer, index, count, or link as one committed transition. A failure before that final stage returns through the declared error channel and leaves every observer with its old answer. This discipline is important even when the program terminates on error, because it makes local reasoning possible and supports a later change to a recoverable interface.

A stack is a disciplined top-only structure

A stack restricts access to its most recently inserted element. The restriction lets a client predict the next removal without knowing the storage layout.

These are conceptual operations. The C header below exposes a smaller interface without top; an interface may instead offer that observer as Peek. A client can call only the operations its actual header declares.

The key law is LIFO, last in first out. If a is pushed before b, then b must come out first unless an error interrupts the process.

Write the abstract stack state as a sequence from bottom to top. For a valid, initialized stack with state S, Push(S, x) has postcondition S' = S · x. For Pop(S), the precondition is S != []; if S = T · x, the postcondition is that x is returned and S' = T.

Complete stack operation contracts

Construction returns an initialized empty state whose depth is zero. Depth and emptiness are observers: they require a valid stack handle, return information about the current sequence, and leave that sequence unchanged. The top observer also preserves state but requires a non-empty sequence. Push is a mutator whose successful postcondition adds exactly one newest element; pop removes exactly that element. A clear operation, when offered, leaves the sequence empty and must dispose of representation-owned resources according to the ownership policy. None of these semantic postconditions determines whether storage is an array or a chain of nodes.

Observer contracts deserve the same precision as mutator contracts. Repeated depth or emptiness queries must be idempotent: calling them twice without an intervening mutator returns the same result and cannot allocate, remove, or reorder elements. A top query has a non-empty precondition but does not transfer ownership of the stored value. If the element type is a pointer, returning that pointer does not by itself say whether the caller may free the pointed-to object. Such ownership rules belong beside the ADT contract because two representations can otherwise appear behaviorally equal while managing payload lifetimes differently.

Mutator postconditions should also state what is preserved, not only what is changed. After push, every old element has the same relative order and the new element alone is newest. After pop, all elements below the removed top retain their order and values. After clear, the abstract sequence is empty, yet the object remains a valid stack that may be reused unless the interface explicitly defines clear as destruction. A separate destructor releases the stack object itself and makes later use invalid. Keeping clear and destruction distinct prevents accidental use-after-free reasoning.

The stack interface hides the representation

An opaque handle prevents client code from depending on internal fields:

typedef struct stackCDT *stackADT;
typedef int stackElementT;

stackADT EmptyStack(void);
void Push(stackADT stack, stackElementT element);
stackElementT Pop(stackADT stack);
int StackDepth(stackADT stack);
int StackIsEmpty(stackADT stack);

stackADT points to an incomplete structure. Client code can hold and pass the handle but cannot access its fields. A fixed array, a dynamic array, and a linked representation can therefore expose the same declarations.

Representation independence concerns observable behavior. It does not imply equal cost: a fixed array, dynamic array, and linked representation may differ in hidden capacity, allocation, and running time. However, if one rejects a particular push while another accepts it, that success/failure difference is observable. The implementations are independent under one strong contract only when their outcomes match, or when capacity and its failure policy are explicitly parameterized or excluded from the shared abstraction. A client may rely on a complexity bound only when that bound is also part of the contract.

How the stack is implemented in practice

A fixed-array implementation stores values bottom to top and keeps a count field for the current depth:

struct stackCDT {
   stackElementT elements[100];
   int count;
};

This version has invariant 0 <= count <= 100. A push is permitted to write an array slot only when count < 100; otherwise the implementation must follow its declared overflow policy before any write occurs.

For a fixed array, the valid region is exactly the prefix whose length is the count. Positions beyond that prefix may contain stale bits, but they are not abstract elements and must never be returned by an observer. Push writes at the first position outside the old prefix and increments the count only after the write is valid. Pop decrements the logical length and returns the former last prefix value; erasing that slot is optional because the reduced count already hides it. At full capacity, however, even the first write is forbidden until the overflow policy has selected a safe outcome.

A dynamic-array version stores an expandable pointer and a size field:

struct stackCDT {
   stackElementT *elements;
   int count;
   int size;
};

When the array fills, Push() may expand the storage with realloc(). The dynamic representation must maintain 0 <= count <= size. If size == 0, it must also have count == 0 and may use elements == NULL; if size > 0, elements must refer to valid storage for at least size values.

#include <limits.h>
#include <stdint.h>
#include <stdlib.h>

/* StackError reports the error and does not return. */
void Push(stackADT stack, stackElementT element) {
   if (stack->count == stack->size) {
      if (stack->size > INT_MAX - 10) {
         StackError("capacity overflow");
      }
      int newSize = stack->size + 10;
      stackElementT *grown;
      if ((size_t)newSize > SIZE_MAX / sizeof *grown) {
         StackError("allocation-size overflow");
      }
      size_t newBytes = (size_t)newSize * sizeof *grown;
      grown = realloc(stack->elements, newBytes);
      if (grown == NULL) {
         StackError("allocation failure");
      }
      stack->elements = grown;
      stack->size = newSize;
   }
   stack->elements[stack->count] = element;
   stack->count++;
}

stackElementT Pop(stackADT stack) {
   if (StackIsEmpty(stack)) {
      StackError("stack underflow");
   }
   return stack->elements[--stack->count];
}

Why geometric growth changes amortized cost

One resize of a stack containing many elements is expensive because all current values may be copied. Amortized analysis distributes that occasional work over the inexpensive pushes that preceded it. If capacity grows geometrically, the successive copied sizes form a geometric sum bounded by a constant multiple of the final depth, so a long legal push sequence has constant average cost per push. Increasing capacity by a fixed amount triggers proportionally many more resizes and can copy a quadratic total. This performance argument is separate from failure atomicity: regardless of the growth rule, a failed resize must not commit a new capacity or lose the old block.

The aggregate argument can be made concrete by considering capacities one, two, four, eight, and so on. Before the array reaches a final capacity, the numbers of copied elements are bounded by the sum of the preceding capacities. That sum is smaller than the next capacity, so all resizing work over the whole prefix of pushes is proportional to the number of stored elements. The single push that triggers a resize is still linear in the current depth; amortized constant time does not claim that every individual push is constant-time.

Shrinking needs a separate policy. Contracting immediately after every pop can make alternating push and pop repeatedly copy the same values. A lower shrink threshold creates hysteresis: capacity grows at a full boundary but shrinks only when utilization is substantially lower. If a shrink allocation fails, the implementation can safely retain the larger block because that block still represents the promised sequence. Thus failed growth prevents insertion, whereas failed optional shrink need not make a successful pop fail.

Linked storage and a different cost model

Growth changes storage identity, not element order. A linked stack instead requires an acyclic chain with its first node representing the top. Its simulation relation is different: following next links from the top produces the reverse of the bottom-to-top abstract sequence. Push installs one new head; pop detaches one old head. If depth is stored, every successful link change must update depth in the same commit. If depth is computed by traversal, its result is linear-time rather than constant-time. Both choices can satisfy exactly the same observer postcondition. Fixed-array push and pop take constant time when legal; a linked stack also changes only one node, but allocation and locality differ from contiguous storage.

Error channels and rejected updates

Underflow and overflow policies must be uniform across the whole interface. A terminating policy should report the cause and stop before mutation. A recoverable policy should return a status separately from the element value, so every possible element remains representable. Exceptions are not a built-in C mechanism, and silently returning an arbitrary value is not a contract. For a bounded queue, full capacity is an expected state; for a dynamic structure, allocation failure is a resource event. They may share a reporting mechanism, but neither may leave counters, indices, or links half updated.

A sentinel can also be a legal element value. Returning status separately from the element avoids that ambiguity; the non-returning handler used above instead makes recovery impossible. Mixing these policies across operations prevents client code from reasoning uniformly about failure.

Capacity overflow and arithmetic overflow must also be distinguished. The first means the representation has no permitted free slot. The second means the proposed capacity or byte size cannot be represented safely, even before memory is requested. Allocation failure means a representable request was not satisfied. All three reject the insertion before its abstract append occurs, but diagnostics and recovery choices may differ. Naming these cases explicitly turns vague error handling into a testable part of the ADT contract.

A stack application: reverse Polish notation

In reverse Polish notation, operands arrive before their operator. The most recent operand is the right operand, so ApplyOperator pops it first and the left operand second. This uses the stack contract without accessing stack fields.

void ApplyOperator(char c, stackADT stack) {
   /* Checked before either Pop: depth >= 2; c is supported;
      the selected result is representable as int; for division,
      y != 0 and the operand pair is not INT_MIN, -1. */
   int y = Pop(stack);
   int x = Pop(stack);

   switch (c) {
   case '+': Push(stack, x + y); break;
   case '-': Push(stack, x - y); break;
   case '*': Push(stack, x * y); break;
   case '/': Push(stack, x / y); break;
   }
}

For a well-formed input, the postcondition is that the two top operands are replaced by their result and all lower operands keep their order. Before either pop, the caller must establish that the chosen +, -, or * result is representable as int; division additionally requires a nonzero divisor and must reject INT_MIN / -1. These checks prevent signed-overflow undefined behavior as well as division by zero.

FIFO requires access at both ends

A work queue must remove the earliest item still waiting, even when new items arrive. This FIFO rule requires insertion and removal at opposite logical ends.

Write the abstract queue state from head to tail. Enqueue(Q, x) has postcondition Q' = Q · x. Dequeue(Q) requires Q != []; if Q = x · R, it returns x and leaves Q' = R. As with top, the conceptual observer front is not declared in the smaller C header shown next.

A queue header can use the same opaque-style pattern:

typedef struct queueCDT *queueADT;
typedef int queueElementT;

queueADT EmptyQueue(void);
void Enqueue(queueADT queue, queueElementT element);
queueElementT Dequeue(queueADT queue);
int QueueLength(queueADT queue);
int QueueIsEmpty(queueADT queue);

Again, the interface says what the user may do; it does not say how the queue is stored.

Complete queue operation contracts

Construction returns an empty head-to-tail sequence. Length and emptiness are non-mutating observers, and the front observer additionally requires a non-empty queue. Successful enqueue appends exactly one element at the tail; successful dequeue returns and removes exactly the head. Clear leaves an empty sequence. Overflow, underflow, and allocation failure must follow the declared policy without exposing a partially updated sequence. These statements remain the same for linear arrays, circular arrays, dynamic arrays, and linked queues.

Why LIFO and FIFO survive every legal update

Proceed by induction on the number of operations. With zero operations, both states are empty and the claim is immediate. Assume it holds after k operations. A stack push appends one value to the right end of the bottom-to-top sequence, and a legal pop removes exactly that rightmost value. A queue enqueue appends at the right end of the head-to-tail sequence, while a legal dequeue removes exactly its leftmost value. Observers such as top, front, and isEmpty do not alter either sequence. Thus each possible next operation preserves the stated return rule and the relative order of survivors, completing the induction.

typedef struct {
  int data[100];
  int top;
} Stack;

void push(Stack *s, int x) {
  s->data[++(s->top)] = x;
}

int pop(Stack *s) {
  return s->data[(s->top)--];
}

Queue implementations: array, circular array, linked list

Repeated removal from the front exposes a storage problem that a stack does not have: unused space can accumulate before the next element.

• A non-circular fixed array either shifts elements on removal or eventually strands unused slots before front.
• A circular array stores logical item i at (front + i) % capacity. With an explicit count, empty means count == 0, full means count == capacity, enqueue writes at (front + count) % capacity, and dequeue advances front modulo the capacity. Its invariant requires capacity > 0, 0 <= front < capacity, and 0 <= count <= capacity before any modulo expression is evaluated. A zero-capacity dynamic queue must grow first. No surviving element moves.
• A dynamic circular array uses the same logical invariant and grows only when full; a growth step may copy the logical sequence into a larger block.
• A linked-list queue stores head and tail pointers and grows as long as the heap can provide memory.

Why circular storage needs no shifting

Consider a capacity-five queue whose front is at physical position three and whose count is four. Its logical elements occupy positions three, four, zero, and one in that order, and the next free position is two. Removing the front advances the front to position four and reduces the count to three; the values at positions four, zero, and one do not move. A later insertion writes position two. This trace illustrates why physical index order and logical FIFO order are different and why printing the raw array is not a valid queue observer.

The no-shift property follows for every valid positive-capacity state, not only this example. Before a removal, old logical rank r + 1 is stored at (front + (r + 1)) % capacity. After the front advances, that survivor has new rank r and is described by the same physical position. Therefore every survivor is already in its correct new logical position. In the chosen count-based design, count bounds every logical rank, identifies the next insertion position, and disambiguates empty from full; other circular designs may reserve a slot or use a full flag instead. During dynamic growth, copying logical ranks in order to a new prefix and then setting the new front to zero establishes the same invariant in the larger block. The new storage and indices are published only after allocation and copying succeed.

The linked-list version is especially useful when we want the queue to keep accepting work items without shifting existing elements around.

struct cellT {
   queueElementT element;
   struct cellT *next;
};

struct queueCDT {
   struct cellT *head;
   struct cellT *tail;
};

The empty representation requires both head == NULL and tail == NULL, so QueueIsEmpty() can test head == NULL. Each update must preserve this agreement when crossing the empty/one-node boundary.

With head and tail, linked enqueue and dequeue are constant-time. This two-field representation computes QueueLength by traversal, which is linear; storing and maintaining a count makes length constant-time at the cost of one more representation invariant.

Linked transition ordering and queue length

A new node is allocated and initialized before either queue endpoint changes. The boundary cases determine which links must then be updated.

The empty-to-one transition is special because there is no old tail through which to link the new node. After allocation succeeds, both endpoints must be published as the new node. The one-to-many transition links through the old tail before replacing the tail pointer, so the new node is reachable throughout the commit. For later insertions the same non-empty case repeats. Allocation failure occurs before either endpoint changes, which directly proves failure atomicity for enqueue.

Removal has a dual case analysis. In a many-node queue, advancing the head keeps the old tail valid. In a one-node queue, the saved successor is null, so both endpoints must become null before the old node is released. The element value must be copied out while the node is still alive. Clear repeats this safe detachment until no node remains or uses an equivalent traversal, then restores the two-null empty invariant and a zero count. If length is stored, forgetting any one of these count updates creates an inconsistency that may not appear until a later observer or full-state check, which is why count belongs in the formal representation invariant.

Function pointers support callbacks and real dispatch

A container can determine which entries to visit without determining what a client wants to do with each entry. A callback supplies that operation at run time while retaining a checked function signature.

At a minimum, a function pointer stores the address of code:

int (*fp)(int);

Parentheses distinguish a pointer to a function from a function returning a pointer. A typedef makes the contract easier to read:

typedef int (*intToIntFnT)(int);
int square(int x) { return x * x; } /* Here x * x must fit in int. */
intToIntFnT fp = square;
int value = fp(3);

For example, a dictionary can traverse its entries while a callback prints or otherwise processes each association. Its bucket layout is irrelevant to the client; the hash-table representation can be developed separately from this interface.

typedef void (*hashtableFnT)(char *, void *);

/* Precondition: fp != NULL. Keys are borrowed and read-only. */
void ForEachEntryDo(hashtableFnT fp, hashtableADT table);

void PrintEntry(char *key, void *value) {
   printf("%s\t%d\n", key, *((int *)value));
}

Client code can pass a callback:

void DisplayWordCount(hashtableADT table) {
   ForEachEntryDo(PrintEntry, table);
}

This lets the implementation own traversal while the client owns entry-specific behavior. The prototype checks the call shape, but void * still erases the payload type; PrintEntry must restore and use the correct pointee type.

A command-dispatch application stores a pointer to a cmdEntryT wrapper as the object value associated with each command name. The wrapper, rather than the hash-table object pointer itself, contains the cmdFnT function pointer:

typedef void (*cmdFnT)(void);
typedef struct { cmdFnT fp; } cmdEntryT;

void ExecuteCommand(char *cmd, hashtableADT commands) {
   cmdEntryT *entry = (cmdEntryT *)Lookup(commands, cmd);
   if (entry == NULL || entry->fp == NULL) {
      printf("Undefined command: %s\n", cmd);
      return;
   }
   entry->fp();
}

Unlike the RPN switch, this is genuine function-pointer dispatch: lookup selects a compatible function and the call goes through the stored pointer.

Signature boundary and dispatch-table lifecycle

Compatibility covers the complete function type: parameter types, return type, and the prototype used at the call site must agree. A cast cannot make an incompatible call safe. Here ForEachEntryDo requires a non-null callback, visits every entry exactly once in an explicitly unspecified order, and forbids structural or key mutation during traversal. Each key and payload pointer is borrowed and valid for the callback call only unless a wider lifetime is documented. Although the legacy signature exposes char *, the callback must treat the key bytes as read-only and must not retain, free, or rewrite them. The payload's actual type and ownership remain part of the surrounding ADT contract because void * carries no run-time type proof.

Having the same number of arguments is not sufficient: a call through an incompatible function type has undefined behavior. A table intended for several command shapes therefore cannot pretend they all share one signature. It needs a genuinely common wrapper signature or separate typed tables. A no-argument command type should explicitly say that it accepts no arguments, rather than use an old-style unspecified parameter list.

A generic payload pointer contains no type tag, object size, destructor, or ownership rule. The surrounding ADT and application contract must supply those facts; traversal alone cannot establish that PrintEntry may read an int.

A dispatch table begins in a valid empty registration state. Registration associates a command key with a table-owned cmdEntryT wrapper containing a non-null compatible function and resolves duplicate keys according to a documented replace-or-reject policy. The wrapper remains valid until its entry is removed or the table is destroyed; the function address is non-owning. The shown wrapper has no context. If a later wrapper adds one, registration must also define whether the table owns it and which destructor removal invokes. Execution handles an absent wrapper or null entry->fp without an indirect call, then invokes exactly the selected entry. This lifecycle is what makes the table an extensible alternative to a growing chain of conditionals; merely writing a switch statement does not create these registration and lookup semantics.

Testing an ADT contract with code

A representation change can be checked by applying the same operation sequence and comparing the returned values and states visible through the interface.

One practical method is to write tiny trace-based tests:

stackADT s = EmptyStack();
Push(s, 10);
Push(s, 20);
assert(StackDepth(s) == 2);
assert(Pop(s) == 20);
assert(Pop(s) == 10);
assert(StackIsEmpty(s));

This kind of test is valuable because it checks the contract at the ADT level, not the memory layout level. If you later replace the array-backed stack with a linked representation, the same test should still pass unchanged.

The same idea applies to queues: a short enqueue, enqueue, dequeue, dequeue trace should confirm that the first inserted element is still the first one removed, even after the representation changes.

A representation-independent contract-test matrix

A useful common black-box suite checks empty construction, repeated observers, one-element removal, many-element order, and the shared success/failure policy. After every rejected operation it repeats depth, length, and—where exported and their non-empty preconditions hold—top or front, verifying failure atomicity without inspecting fields. Representation-specific tests are separate: a fixed backend can be filled to overflow, an instrumented allocator can fail dynamic growth, a circular backend can cross its wrap boundary, and a linked backend can exercise the one-node pointer transition. These configured cases cannot all be imposed unchanged on every backend. Complexity measurements also belong in a separate suite because equal results do not imply equal allocation, traversal, or resize costs. Function pointers are needed only if the harness deliberately uses an operations table to choose an implementation at run time.

A model-based test makes the oracle explicit. The test maintains a simple sequence in ordinary test code, applies each requested operation both to that model and to the ADT, and compares every returned value and observer result. Because the oracle expresses only the contract, it can validate an array stack, a linked stack, a circular queue, or a linked queue without knowing their fields. Generated traces can repeatedly cross empty, one-element, and many-element boundaries, where pointer and index bugs are most likely.

Failure tests require controlled causes. A bounded representation can be filled to force overflow; an allocation layer can be instructed to fail the next growth or node request. After the rejected operation, the test repeats all observers and then continues with legal operations, proving that the object was not merely unchanged in appearance but remains usable. Callback tests separately record visited entries and payload identities. Dispatch tests register known commands, exercise unknown keys, and verify replacement policy. Timing and allocation counts are measured separately from semantic equality, so a slower correct implementation does not fail a behavior test and a fast incorrect one does not pass.

Common mistakes

Quick checks

Exercises

Summary

ADT contracts define legal state transitions and failure behavior. Stack and queue implementations must preserve their LIFO/FIFO sequence invariants even when their storage and costs differ. Function pointers add signature-checked callbacks and dispatch; they do not replace the ADT interface that provides representation independence.