Physical and logical structures

Is a stack a kind of memory? Watch the same seven numbers become a stack, a queue and a tree without moving.

The layout and the rules

The seven numbers never move. What makes them a stack, a queue or a tree is the rule you use to read them: where the next one goes in and which one comes out. A data structure has two parts, and it helps to keep them apart:

• the physical structure: how the values sit in memory;
• the logical structure: the rules for adding, finding and removing them.

Two layouts in memory

Memory gives you two ways to keep many values.

• Contiguous: the values side by side in one block, an array. Cell i is found by arithmetic, one address plus i times the size of a cell.
• Linked: each value in a node of its own, anywhere in the heap, holding the address of the next node. Linked lists, from chapter 7 on, are built this way.

Either layout can carry any of the logical structures below. Stacks built a stack both ways.

Four logical families

• Linear: one value after another. A stack takes from the end it last added to; a queue takes from the other end.
• Hierarchical: a tree, each value but the root with one parent, and any number of children.
• Network: a graph, any value joined to any other.
• Table: values found by a key, as hashing does.

Read as a tree, the seven cells follow one rule: cell i is the parent of cells 2i + 1 and 2i + 2. So 30, in cell 1, has the children in cells 3 and 4, 20 and 40. That tree happens to be the search tree of a later chapter, kept in an array with no pointers at all.

An abstract data type in C

An abstract data type (ADT) is a list of operations and what they mean, with nothing said about storage. A stack’s is: make an empty stack, push a value, pop the value pushed last, ask whether it is empty. The same ADT can sit on an array or on linked nodes; the operations do not fix the storage.

C has no keyword for this. The pattern is two files and a promise.

The header: what the user may call

#ifndef STACK_H
#define STACK_H

#include <stdbool.h>

struct stack;

struct stack *stack_new(void);
void stack_free(struct stack *s);
bool push(struct stack *s, int v);
int pop(struct stack *s);
bool is_empty(const struct stack *s);

#endif

stack.h declares the five operations and nothing else. The line struct stack; says that a type with that name exists, without saying what is in it: an incomplete type. A file that includes the header may hold a struct stack *, a pointer, because C gives every pointer to a struct the same size and representation, whatever the struct holds. It cannot make a struct stack or look inside one, because it does not know the type’s size or fields. The #ifndef lines stop the header being read twice in one file.

The source: how it is stored

#include <stdlib.h>
#include "stack.h"

#define CAP 16

struct stack {
    int items[CAP];
    int top;
};

struct stack *stack_new(void)
{
    struct stack *s = malloc(sizeof *s);
    if (s != NULL)
        s->top = 0;
    return s;
}

void stack_free(struct stack *s)
{
    free(s);
}

static bool is_full(const struct stack *s)
{
    return s->top == CAP;
}

bool push(struct stack *s, int v)
{
    if (is_full(s))
        return false;
    s->items[s->top] = v;
    s->top = s->top + 1;
    return true;
}

int pop(struct stack *s)
{
    s->top = s->top - 1;
    return s->items[s->top];
}

bool is_empty(const struct stack *s)
{
    return s->top == 0;
}

stack.c completes the type, an array of 16 ints and a top, and defines the five functions. pop does not check for an empty stack: popping one is undefined behaviour (here it reads items[-1]; in the linked version below, it follows a NULL pointer). The caller must ask is_empty first. is_full is marked static: it can be called only from inside stack.c, so it is not part of the ADT, and another file may use the same name for something else.

The user’s file

#include <stdio.h>
#include "stack.h"

int main(void)
{
    struct stack *s = stack_new();
    if (s == NULL)
        return 1;
    for (int v = 1; v <= 3; v++)
        push(s, v * 10);
    while (!is_empty(s))
        printf("%d ", pop(s));
    printf("\n");
    stack_free(s);
    return 0;
}

main.c includes the header and uses only the five operations. It never learns that there is an array inside.

Compiling and linking

Each .c file is compiled on its own into an object file, machine code with the names it defines and the names it still needs. The linker then joins the object files and matches each needed name to its definition.

gcc -std=c11 -Wall -Wextra -c stack.c
gcc -std=c11 -Wall -Wextra -c main.c
gcc stack.o main.o -o stacktest
./stacktest

The first two commands make stack.o and main.o, and neither is a program yet: stack.o has no main, and main.o calls functions it does not define. The third links them. The program prints 30 20 10 : pushed 10, 20, 30, popped last first.

stack.h is never compiled by itself. The preprocessor copies it into each file that includes it, so the declarations are the same in both.

Worked example

Sort the structures. An editor’s undo history is a stack: the last change is undone first. The jobs waiting for a printer are a queue: first sent, first printed. Folders on a disk are a tree. Roads between towns are a graph. A phone book looked up by name is a table.

Look inside, and fail. A user writes peek-inside.c, which includes stack.h and tries s->top = 0;. It does not compile:

peek-inside.c:9:6: error: invalid use of undefined type 'struct stack'

main.c and peek-inside.c see only the incomplete type, so the fields do not exist for them. The array stays in stack.c’s hands.

Change the storage, keep the user. stack-linked.c puts the stack of Stacks on linked nodes behind the same five functions: struct stack now holds only a pointer to the top node, push allocates a node, and pop frees one. Link it in place of stack.c:

gcc -std=c11 -Wall -Wextra -c stack-linked.c
gcc stack-linked.o main.o -o stacktest

main.c is not edited and main.o is not even recompiled; it is only linked again. The program prints 30 20 10 as before.

What changes is the memory. The array version is one 68-byte block (16 ints and top) whether it holds 1 item or 16. The linked version is an 8-byte struct stack plus one 16-byte node per item, each a block of its own from malloc, and it has no limit of 16.

Three checks. Read as a tree, what are 30’s children? (20 and 40.) Which file must change for the stack to hold 32 items? (stack.c only: CAP.) Why can main.c hold a struct stack * but not a struct stack? (Its size is unknown there.)

Where it’s used

The C library. FILE, behind fopen, fprintf and fclose, is used only through pointers and functions; programs never reach into it.

Operating systems. Files, sockets and processes are handed to programs as handles, with operations on them and nothing else.

Shared code. A team that publishes a header can rewrite its source, faster or smaller, and every program that uses it only needs linking again.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.