1.1 ADT operations: stack, queue, and function pointers

Why this section starts with contracts

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.

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.

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.

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.

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.

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 is simple, but it has a hard capacity limit. If the depth grows beyond 100, the implementation hits stack overflow at the representation level, not the mathematical stack operation.

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() expands the storage with realloc(). That gives the client a larger logical stack without changing the interface.

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.

void Push(stackADT stack, stackElementT element) {
   if (stack->count == stack->size) {
      stack->size += 10;
      stack->elements = realloc(
         stack->elements,
         stack->size * sizeof(stackElementT)
      );
   }
   stack->elements[stack->count] = element;
   stack->count++;
}

stackElementT Pop(stackADT stack) {
   stack->count--;
   return stack->elements[stack->count];
}

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.

The lecture notes present the queue header in 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.

Queue implementations: array, circular array, linked list

The tutorial slides make the implementation tradeoffs explicit.

• A fixed-size array is the simplest first version, but it wastes space when elements are dequeued from the front and new values are appended at the tail.
• A circular array fixes that waste by wrapping front and rear around with the modulus operator.
• A linked-list queue stores head and tail pointers and grows as long as the heap can provide memory.

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

That representation makes enqueue and dequeue conceptually simple:

• a new node is linked at the tail,
• the head node is removed and freed,
• QueueIsEmpty() is just $head == NULL$.

Function pointers let C simulate method dispatch and callbacks

The lecture on function pointers is not random extra material. It explains how C can defer behavior until runtime while still staying type-safe.

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

int (*fp)(int);

The pointer may point to any function with the matching prototype. That means the type signature is the contract.

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

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

void ForEachEntryDo(hashtableFnT fp, hashtableADT table);

Client code can pass a callback:

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

This pattern matters for ADTs because it lets the implementation perform the iteration while the client controls what happens to each entry. The traversal logic stays in one place, but the action can vary.

The same idea also appears in dispatch tables: a set of function pointers can select the correct operation for a specific structure or command without a long chain of if statements.

void ApplyOperator(char c, stackADT stack) {
   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;
   }
}

In this example, the stack stores operands while the operation table decides how to combine them. The code is small, but the concept is broad: function pointers turn C into a manually controlled dispatch system.

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.

Common mistakes

Quick checks

Exercises

Takeaway

The main idea is not “stack and queue are two data structures.” The real idea is that ADT contracts define behavior, implementations choose storage, and function pointers let C separate those responsibilities without losing control over the types.