1.1 ADT operations: stack, queue, and function pointers

Motivation

In CSCI2520, the first mistake is usually not a missing semicolon. It is a missing contract.

An abstract data type tells us four things before we commit to a particular representation:

• what operations are legal,
• what each operation guarantees,
• what the client may assume after a call,
• how empty-state and error cases are handled.

The last item is part of correctness, not an implementation footnote. A precondition states what must be true before an operation; a postcondition states what the operation returns and which abstract state must remain afterward. If a precondition can fail, the interface must also prescribe an observable failure policy.

That separation matters because the same stack or queue interface can be backed by a fixed array, a dynamic array, or a linked list. The client code should not need to change when the representation changes.

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

The lecture slides define a stack as a pile that can be accessed only from the top. That is not just an analogy. It is the invariant that makes stack code predictable.

These are the conceptual operations. The course header shown below exposes a smaller interface without top; Tutorial 2 calls the corresponding observer Peek. Either choice is valid only when the exact public interface is stated consistently.

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

The lecture makes a point of the opaque type pattern:

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);

This is not cosmetic. stackADT is a pointer to an incomplete structure, so the client can hold and pass stacks around but cannot reach inside the structure. That means the implementation can change from:

• a fixed array of 100 entries,
• to a dynamic array with realloc,
• to another internal layout later,

without rewriting client code.

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.

Representation invariants and cost models

A fixed array relates its concrete prefix to the abstract sequence and keeps a count within the capacity. A dynamic array adds the requirement that its allocation can hold every position below the capacity. A linked stack instead requires an acyclic chain whose first node represents the abstract top; a stored count, if present, must equal the number of reachable nodes. Fixed-array push and pop are constant-time but bounded. Dynamic growth occasionally copies the current sequence. Linked operations avoid bulk copying but allocate or release one node and have different locality. These cost differences do not alter LIFO behavior.

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 uses the same prefix relation plus a capacity relation. An empty dynamic stack may own a small allocation or may use a null pointer with zero capacity, but the chosen convention must be represented consistently. Growth changes storage identity, not element order. A linked stack uses a different simulation relation: 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.

How the stack is implemented in practice

The source slides show three important implementation ideas.

First, 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.

Second, 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.

Third, the slides also refine Pop() to recover memory more carefully when the underlying array is no longer fully used. That is a reminder that a correct interface is not enough; memory policy still matters.

#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.

A stack application: reverse Polish notation

The following source example is a stack application, not a function-pointer dispatch table. In reverse Polish notation, operands arrive before their operator. ApplyOperator therefore pops the right operand first and the left operand second.

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.

Queue semantics are different, even if the code looks similar

The queue ADT is the other side of the same design problem. The operations are similar in style, but the invariant is FIFO, first in first out.

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 lecture 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.

Theorem/Proposition

Proof sketch or proof idea

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.

Queue implementations: array, circular array, linked list

The tutorial slides make the implementation tradeoffs explicit.

• 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

For a positive capacity, the circular representation assigns each logical rank a physical position by adding that rank to the front index and reducing modulo the capacity. Enqueue changes only the next free position and the count; dequeue changes only the front index and the count. Every surviving logical rank therefore maps to the same stored value without moving that value. In this representation, the stored count is the chosen way to distinguish empty from full when the indices coincide; other valid designs may reserve one slot or store a separate full flag. When a dynamic circular queue grows, it may copy the logical sequence once into a larger block, but it must publish the new block and indices only after that copy succeeds.

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; those roles may be implemented differently in another valid circular representation. 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 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;
};

Its boundary transitions are part of the representation invariant:

• an empty queue has head == NULL and tail == NULL,
• enqueue into an empty queue sets both pointers to the new node,
• enqueue into a non-empty queue links after tail and advances tail,
• dequeue from a multi-node queue advances head and leaves tail unchanged,
• dequeue of the only node frees it and resets both pointers to NULL,
• QueueIsEmpty() is just head == NULL.

With head and tail, linked enqueue and dequeue are constant-time. The lecture implementation 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

Linked updates must be ordered so that every intermediate state remains owned and reachable. Enqueue allocates and initializes a node before changing either queue pointer. Dequeue saves the old head and its value, advances the head, resets the tail when the queue becomes empty, and only then releases the old node. The same order covers empty, one-node, and many-node cases without a dangling public state. Computing length by traversal needs no extra field but takes time proportional to the number of reachable nodes. A stored count makes the observer constant-time, provided every successful enqueue, dequeue, and clear updates it in the same committed transition.

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

The lecture uses function pointers to defer behavior until runtime 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);

The slides then move to a practical ADT example: extending a hash table with a callback-based traversal operation.

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.

The source’s 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.

Function compatibility is stricter than merely having the same number of arguments. Each parameter and the return type must be compatible under the C function type rules, and the caller must use a prototype that describes those types. Calling through a casted incompatible pointer invokes undefined behavior; the cast only suppresses useful diagnostics. 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.

Callback traversal creates a two-party protocol. The ADT implementation controls bucket and node iteration and supplies each borrowed key and payload; the callback interprets the payload and performs the client action without changing table structure or key bytes. The generic payload pointer crosses only an object boundary; it does not record a type tag, size, destructor, or ownership rule. Those facts must be supplied by the surrounding ADT and application contract.

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.

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)--];
}

Testing an ADT contract with code

Once the interface is fixed, the next question is not “does it compile?” but “does every observable state transition still satisfy the contract?”

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

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.

Choosing an error channel changes the public function signatures. A status return with an output parameter can represent every possible element value and lets the caller decide whether to retry, grow another structure, or propagate the failure. A terminating handler keeps the simpler value-returning interface but makes recovery impossible. These designs are both coherent when documented; mixing them operation by operation is not. In particular, returning a sentinel from one removal and terminating from another prevents generic client code from reasoning uniformly about precondition violations.

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.

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.