08. Abstract Data Types

Abstraction and the C interface#

An abstraction retains the information relevant to a problem and hides details we do not need at that level. A road map can retain intersections and connections while ignoring individual paving stones. A queue retains arrival order while hiding allocation details.

An ADT specifies a collection of possible values, the operations allowed on them, and the meaning of those operations. Its interface is the contract exposed to the client, meaning the code that uses it. An implementation chooses a concrete representation and algorithms that satisfy that contract.

For a C module, put the public declarations in a header such as Stack.h and the private structure and function bodies in Stack.c. A typical header begins:

#ifndef STACK_H
#define STACK_H
#include <stdbool.h>
#include <stddef.h>
typedef struct stack *Stack;
Stack StackNew(void);
void StackFree(Stack s);
void StackPush(Stack s, int value);
int StackPop(Stack s);  // Requires a nonempty stack.
int StackPeek(Stack s); // Requires a nonempty stack; does not remove.
size_t StackSize(Stack s);
bool StackIsEmpty(Stack s);
#endif

struct stack is declared but not defined here. The compiler knows that Stack is a pointer type, so clients can store and pass a handle. Clients cannot inspect s->head, because the fields are unknown. This is an opaque type: the representation is hidden. The header guards prevent repeated inclusion from redeclaring its contents.

The comments matter as much as the types. A precondition says what must be true before a call, such as “the stack is nonempty”. A postcondition says what the call guarantees, such as “the old top item is returned and the stack contains one fewer item”. C cannot infer these semantic rules from int StackPop(Stack s) alone.

The slide's bank-account example shows the same boundary in another domain. An Account.h could expose AccountOpen, AccountBalance, AccountDeposit, AccountWithdraw, and AccountClose without revealing the struct account fields. A client can deposit 50 through the interface, but cannot validly write acc->balance = 1000000: the field is hidden and bypassing the operation's checks would break the account contract. This is the same reason a queue client must call enqueue instead of editing tail itself.

The implementation must maintain a representation invariant: a property that makes its internal state a valid encoding of the abstract value. For a linked stack, the stored size equals the number of reachable nodes, and an empty stack has a null head. Each operation begins and ends in a state satisfying these rules.

Practice. Why is exposing struct stack { int *items; int size; }; in the public header a stronger commitment than exposing only typedef struct stack *Stack;?

Stacks: the most recent unfinished job#

A stack is a last in, first out collection: LIFO. push(x) adds x at the top, pop() removes and returns the top, and peek() returns it without removal. Nothing in the definition requires an array or vertical picture.

Take the lecture sequence push(9), push(2), push(6), pop(), pop(), push(8). Write abstract stack contents from bottom to top:

Step through the same sequence below. Follow the top, rather than whichever end happens to be drawn on the left.

Array and linked representations#

An array stack keeps its live values in items[0..size-1], so the top is at size-1. Push writes items[size] and increments size; pop decrements size and returns that position. Both use constant work if capacity is already available. A fixed-capacity implementation must define what happens when full. C arrays do not grow automatically.

A dynamically growing array can allocate a larger buffer and copy the old values when full. Doubling capacity gives amortised constant push cost: across $m$ pushes, all previous buffers copied have sizes $1,2,4,\ldots$, whose total is less than $2m$. Thus total work is $O(m)$, although an individual resizing push can cost $O(m)$. This is an aggregate guarantee, not an average over random inputs. Pop need not shrink the array; if it does, use a separate shrinking threshold to avoid repeatedly growing and shrinking near one boundary.

A linked stack inserts and removes at the head. In the lecture picture, head is the top, so 6 comes before 2 and 9 in pointer order even though 9 arrived first.

For integer items, the following is the private core of Stack.c. It uses the public Stack typedef above. Allocation failure terminates this teaching implementation; a different API could instead report failure to its caller.

#include <assert.h>
#include <stdlib.h>
struct cell { int value; struct cell *next; };
struct stack { struct cell *head; size_t size; };

Stack StackNew(void) {
    Stack s = malloc(sizeof *s);
    if (s == NULL) abort();
    *s = (struct stack){.head = NULL, .size = 0};
    return s;
}
void StackPush(Stack s, int value) {
    struct cell *p = malloc(sizeof *p);
    if (p == NULL) abort();
    *p = (struct cell){.value = value, .next = s->head};
    s->head = p;
    s->size++;
}
int StackPop(Stack s) {
    assert(s->head != NULL);
    struct cell *old = s->head;
    int value = old->value;
    s->head = old->next;
    free(old);
    s->size--;
    return value;
}
int StackPeek(Stack s) { assert(s->head != NULL); return s->head->value; }
size_t StackSize(Stack s) { return s->size; }
bool StackIsEmpty(Stack s) { return s->size == 0; }
void StackFree(Stack s) {
    while (!StackIsEmpty(s)) (void)StackPop(s);
    free(s);
}

Notice the order in pop: save the successor and value before freeing the old node. free ends its lifetime; reading old->next afterward is invalid. The stack owns the nodes it allocates. The client owns the handle's eventual disposal and must not use it after StackFree.

Each linked push, pop and peek is $O(1)$ under the course's constant-time allocation model. The cached size makes size queries $O(1)$ rather than a traversal. Freeing all $n$ nodes is $\Theta(n)$. Storage is $\Theta(n)$, with a link and allocation overhead per node. Arrays have better contiguous access and less per-item overhead; linked stacks avoid copying their existing items to grow.

Practice. After the sequence above, what does peek() return, what is the size, and which item does the next pop return?

Bracket matching#

Nested brackets are unfinished jobs. Reading ( means “I will eventually need )”; reading [ inside it creates a more recent job that must finish first. This is why a stack matches nesting.

Scan left to right. Push opening brackets. On a closing bracket, reject if the stack is empty; otherwise pop the most recent opening bracket and reject if the types differ. At the end accept only if the stack is empty. The lecture trace for ([{ }]), with spaces ignored, shows each closing bracket cancelling the newest remaining opening bracket.

The loop invariant is that the stack contains exactly the unmatched opening brackets of the prefix already scanned, in their nesting order. An opening bracket extends that sequence. A matching close removes its last element. A mismatched close cannot be repaired by a later character because the prefix already violates nesting.

For ([)], we push ( then [. Reading ) pops [, which needs ], so reject immediately. Merely counting two opens and two closes would wrongly accept it. For ((), every close encountered matches, but an opening bracket remains at the end, so reject. For ()), the last close encounters an empty stack.

For a string of length $m$, each character causes at most one push or pop: $O(m)$ time and $O(m)$ auxiliary storage in the fully nested case. This excludes the input string itself.

Practice. Trace {[()]} and {[(])}. Where does the second input first fail?

Queues: preserve arrival order#

A queue is first in, first out: FIFO. enqueue(x) adds at the rear; dequeue() removes and returns the front. Peek examines the front. Examples include a waiting list and the frontier in breadth-first search.

For enqueue(6), enqueue(8), enqueue(12), dequeue(), enqueue(13), dequeue(), the removals return 6 then 8. The queue ends 12,13, read front to rear. Unlike a stack, a new arrival must not jump ahead of an old arrival.

Linked queue with two endpoints#

Use a head pointer for the front and a tail pointer for the rear. Without a tail pointer, appending requires walking through $n$ nodes, so enqueue is $O(n)$. The tail gives direct access to the place we need to change.

The invariant is: empty means both pointers are null; otherwise head reaches exactly size nodes, tail points to the last, and tail->next is null. For enqueue, allocate a node with null next. If empty, set head to it; otherwise set the old tail's next to it. Finally set tail to it. For dequeue, save the old head, advance head, and free the old node. If that removed the last item, also set tail to null.

Here is the core, with a local representation rather than a separate public header:

struct queue { struct cell *head, *tail; size_t size; };
void enqueue(struct queue *q, int value) {
    struct cell *p = malloc(sizeof *p);
    if (p == NULL) abort();
    *p = (struct cell){.value = value, .next = NULL};
    if (q->tail != NULL) q->tail->next = p;
    else q->head = p;
    q->tail = p;
    q->size++;
}
int dequeue(struct queue *q) {
    assert(q->head != NULL);
    struct cell *old = q->head;
    int value = old->value;
    q->head = old->next;
    if (q->head == NULL) q->tail = NULL;
    free(old);
    q->size--;
    return value;
}

The code shares struct cell and the includes from the stack example. Initialise with struct queue q = {0};; destroy by dequeuing until size is zero. A public Queue module can hide the representation exactly as Stack does.

The next lecture example uses 8,23,12: two dequeues return 8 and 23, and enqueueing 15 produces the diagram below. Head now points to 12 and tail to 15.

Each endpoint operation and cached size query is $O(1)$; freeing all items is $\Theta(n)$ and node storage is $\Theta(n)$.

Practice. Why can we not get an equally fast singly linked queue by inserting at the head and removing at the tail, even if we keep a tail pointer?

Array queues and reused space#

If live items always start at index zero, dequeue shifts every remaining item left and costs $\Theta(n)$. Instead keep a moving front index. The lecture diagram has already removed 8 and 23, so front is 2 and the live items are 12 and 15. The old slots are outside the queue; clearing their bytes is unnecessary for integer values.

Moving front makes a dequeue constant time, but an ever-increasing front wastes the emptied slots. A circular buffer reuses them. With positive capacity $c$, store the live count $n$ and front index $f$. Logical item $i$ occupies (f+i)%c; enqueue uses (f+n)%c, while dequeue advances f=(f+1)%c. The count distinguishes empty ($n=0$) from full ($n=c$), even when their endpoint indices coincide.

For capacity 4, front 2 and live items 12 at slot 2, 15 at slot 3, enqueue 19 writes slot (2+2)%4=0. The logical queue is 12,15,19, despite wrapping in physical memory. A resizing queue must copy in logical FIFO order, then reset front to zero. With geometric growth, enqueue is amortised $O(1)$; dequeue is $O(1)$ when no shrinking copy occurs.

Practice. Capacity is 5, front is 4 and size is 3. Which slots contain the three items, and where does the next enqueue write?

Sets: membership without duplicates#

A set is an unordered collection of distinct values. Insert an existing value and the abstract set stays unchanged. Delete a missing value and it also stays unchanged. A set can be stored in sorted order without promising an insertion order to its client.

For input 7,2,7,4,2, the set has three values, $\{2,4,7\}$. The important result is membership and size, not whichever order a display function chooses. Sets are useful for counting distinct inputs, recording visited vertices, or testing membership.

Three initial representations#

The slide interface has SetNew, SetFree, SetInsert, SetDelete, SetContains, SetSize, and SetShow. A client can read integers until end-of-file, insert each one, then use SetSize to count distinct inputs. SetShow is free to display them in any order because the set contract specifies membership, not order. Each implementation below must make duplicate insertion and absent deletion harmless.

An unordered array searches linearly for a value. Insert must first check for an existing copy, so a set insertion is $O(n)$ even though the final append is constant work. To delete, search for the value then replace its slot with the last live item and reduce size. This destroys position order, which the ADT never promised. Deleting 2 from [7,2,4] gives [7,4] without shifting.

An ordered array uses binary search for contains, giving $O(\log n)$. To insert 4 into [2,5,9], find position 1, move 9 and 5 one slot right, then write 4. Locating the position is fast; moving up to $n$ items is still $O(n)$. Delete similarly shifts the suffix left. If a duplicate is found, insertion ends without shifting.

An ordered linked list walks until reaching the value or the first larger value. It cannot jump to a midpoint in constant time, so it does not acquire array binary-search speed. Search, insertion and deletion are each $O(n)$ overall; once the predecessor is found, relinking itself takes $O(1)$. Insert 4 into 2→5→9 by pointing the new node at 5 and then 2 at the new node.

Here is a complete unordered-array core. The displayed order can change on deletion, exactly as the ADT permits. This version grows geometrically so capacity is not silently assumed to be infinite. It aborts on allocation failure; a production interface could instead return an error. Save it as one C file to experiment, or put the opaque typedef and operation declarations in Set.h and the structure/functions in Set.c.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct set *Set;
struct set { int *items; size_t size, capacity; };

Set SetNew(void) {
    Set s = malloc(sizeof *s);
    if (s == NULL) abort();
    *s = (struct set){0};
    return s;
}
void SetFree(Set s) { free(s->items); free(s); }
size_t SetSize(Set s) { return s->size; }
bool SetContains(Set s, int v) {
    for (size_t i = 0; i < s->size; i++)
        if (s->items[i] == v) return true;
    return false;
}
void SetInsert(Set s, int v) {
    if (SetContains(s, v)) return;
    if (s->size == s->capacity) {
        size_t newCap = s->capacity == 0 ? 4 : s->capacity * 2;
        if (s->capacity > SIZE_MAX / 2 || newCap > SIZE_MAX / sizeof *s->items) abort();
        int *p = realloc(s->items, newCap * sizeof *p);
        if (p == NULL) abort();
        s->items = p;
        s->capacity = newCap;
    }
    s->items[s->size++] = v;
}
void SetDelete(Set s, int v) {
    for (size_t i = 0; i < s->size; i++) {
        if (s->items[i] == v) {
            s->items[i] = s->items[s->size - 1];
            s->size--;
            return;
        }
    }
}
void SetShow(Set s) {
    for (size_t i = 0; i < s->size; i++)
        printf("%s%d", i == 0 ? "" : " ", s->items[i]);
    putchar('\n');
}

SIZE_MAX is the largest value representable by size_t; the checks prevent multiplying or doubling capacity beyond that range. realloc may move the buffer, so s->items is updated from its returned pointer only after success. The old allocation is then managed through the new pointer.

The representation invariant is size <= capacity and each live value occurs once in items[0..size-1]. SetContains scans that interval. SetInsert scans first, then optionally copies the array on growth; a non-resizing append is constant work but the whole insertion is still $O(n)$ because uniqueness must be checked. SetDelete scans before one assignment; it never reads an old slot after size--. Freeing the allocated buffer is $O(1)$ under the allocation model, while destroying a linked representation would walk and free each node.

For an ordered array, use binary search to find the first index whose value is at least v. If it equals v, do nothing; otherwise shift the suffix one place right and write v. For deletion, shift left after the found index. For an ordered linked list, maintain a pointer to the link (Node **link) while advancing through smaller nodes, then insert or unlink at that position. The comparison/search phase is linear there, even though a final link rewrite is constant.

Here $n$ is the number of stored values, capacity handling is assumed valid, and the operation includes finding/checking the value. Storage is $O(n)$ for a capacity proportional to $n$, and basic size queries are $O(1)$ if cached. 09. Binary Search Trees, 11. AVL Trees, and 17. Hash Tables develop other set representations with different guarantees.

Practice. A program performs a million membership queries but only occasionally changes a set. Which of these initial representations is attractive, and why does “set values are unique” alone not guarantee fast searching?

Practice. Complete the unordered-array deletion: after locating an item at index i, why is items[i] = items[size-1]; size--; correct?

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. A bracket checker sees ([)]. List the stack state after the first two characters and explain the first mismatch.

Question 2. A queue uses a circular array of capacity 5, with front=3 and three items. At which indices are the items stored, and where is the next enqueue?

Question 3. An unsorted-array set has n values and no duplicates. Give the cost of membership, insertion and deletion if insertion must preserve the set invariant.