Algol 68 stacks, queues and trees
last modified November 13, 2026
A stack, a queue, and a tree are three answers to the same question: in what order should the values of a collection be kept? A stack keeps the newest on top, a queue keeps the oldest in front, and a tree keeps them so that a search can descend by comparison. All three can be built from the reference and structure that the linked lists article introduced.
This article writes each of them, shows the operations that define it, and looks at why the shape of a tree decides how fast it answers.
A stack
A stack adds and removes at one end, called the top. A reference to the top
node is the whole stack, and push allocates a node whose
next is the old top. pop reads the value of the top
node and moves the reference to the next node, and peek reads the
value without changing anything.
MODE NODE = STRUCT (REF NODE next, INT value);
MODE STACK = REF NODE;
STACK empty = NIL;
PROC push = (REF STACK s, INT value) VOID:
s := HEAP NODE := (s, value);
PROC pop = (REF STACK s, REF INT value) BOOL:
IF s IS empty THEN
FALSE
ELSE
value := value OF s;
s := next OF s;
TRUE
FI;
PROC peek = (STACK s, REF INT value) BOOL:
IF s IS empty THEN
FALSE
ELSE
value := value OF s;
TRUE
FI;
PROC depth = (STACK s) INT:
(
INT n := 0;
STACK p := s;
WHILE p ISNT empty DO
n +:= 1;
p := next OF p
OD;
n
);
BEGIN
STACK s := empty;
push(s, 10);
push(s, 20);
push(s, 30);
INT v;
print((whole(depth(s), 0), " items", newline));
print((peek(s, v), " ", whole(v, 0), newline));
WHILE pop(s, v) DO
print((whole(v, 0), " "))
OD;
print(newline);
print((pop(s, v), " ", whole(depth(s), 0), newline))
END
pop and peek answer whether there was anything to
read and leave their REF INT parameter alone when the stack is
empty. The stack itself is passed as REF STACK to the procedures
that change the top, and by value to the ones that only read it.
The three pushes leave 30 on top, which is what peek reports, and
the pops return the values in the opposite order to their insertion. The last
line shows that an empty stack answers F and that its depth is 0.
$ a68g stack.a68 3 items T 30 30 20 10 F 0
A queue
A queue adds at the tail and removes at the head, so it hands values back in
the order they arrived. Two references, one to each end, make both operations
constant time, and a structure of mode QUEUE keeps them together.
MODE NODE = STRUCT (REF NODE next, INT value);
MODE QUEUE = STRUCT (REF NODE head, tail);
REF NODE empty = NIL;
PROC enqueue = (REF QUEUE q, INT value) VOID:
(
REF NODE n := HEAP NODE := (empty, value);
IF head OF q IS empty THEN
head OF q := n
ELSE
next OF (tail OF q) := n
FI;
tail OF q := n
);
PROC dequeue = (REF QUEUE q, REF INT value) BOOL:
IF head OF q IS empty THEN
FALSE
ELSE
REF NODE first := head OF q;
value := value OF first;
head OF q := next OF first;
IF head OF q IS empty THEN
tail OF q := empty
FI;
TRUE
FI;
PROC size = (QUEUE q) INT:
(
INT n := 0;
REF NODE p := head OF q;
WHILE p ISNT empty DO
n +:= 1;
p := next OF p
OD;
n
);
BEGIN
QUEUE q;
q := (empty, empty);
FOR i TO 4 DO
enqueue(q, i * 10)
OD;
print((whole(size(q), 0), " queued", newline));
INT v;
print((dequeue(q, v), " ", whole(v, 0), newline));
enqueue(q, 50);
WHILE dequeue(q, v) DO
print((whole(v, 0), " "))
OD;
print(newline);
print((dequeue(q, v), " ", whole(size(q), 0), newline))
END
A new node is linked after the tail and becomes the new tail. Removal moves the head to the next node and resets the tail when the queue becomes empty, since otherwise the tail would still point at the node that was just removed and the next insertion would link to a node outside the queue.
Four values are queued and 10 is removed, which leaves 20 30 40. The 50 that is added afterwards goes to the end, so the remaining order is 20 30 40 50. The final line shows the empty queue, where a removal fails and the size is 0.
$ a68g queue.a68 4 queued T 10 20 30 40 50 F 0
A binary search tree
A binary search tree keeps values smaller than a node in its left subtree and
larger ones in its right subtree, so a search follows a single path from the
root. insert compares, descends into the appropriate subtree, and
allocates a leaf when it reaches an empty one. The parameter is
REF BST, which lets the call attach the new node to the field of
its parent.
MODE TREE = STRUCT (REF TREE left, right, INT value);
MODE BST = REF TREE;
BST empty tree = NIL;
PROC insert = (REF BST t, INT value) VOID:
IF t IS empty tree THEN
t := HEAP TREE := (empty tree, empty tree, value)
ELIF value < value OF t THEN
insert(left OF t, value)
ELIF value > value OF t THEN
insert(right OF t, value)
FI;
PROC walk = (BST t) VOID:
IF t ISNT empty tree THEN
walk(left OF t);
print((whole(value OF t, 0), " "));
walk(right OF t)
FI;
PROC height = (BST t) INT:
IF t IS empty tree THEN
0
ELSE
INT l = height(left OF t);
INT r = height(right OF t);
1 + IF l > r THEN l ELSE r FI
FI;
PROC contains = (BST t, INT value) BOOL:
IF t IS empty tree THEN
FALSE
ELIF value = value OF t THEN
TRUE
ELIF value < value OF t THEN
contains(left OF t, value)
ELSE
contains(right OF t, value)
FI;
BEGIN
BST t := empty tree;
[1:7] INT values := (50, 30, 70, 20, 40, 60, 80);
FOR i TO UPB values DO
insert(t, values[i])
OD;
print((whole(height(t), 0), newline));
walk(t);
print(newline);
print((contains(t, 40), " ", contains(t, 45), newline))
END
walk prints the values in order because it visits the left
subtree, then the node, then the right subtree. contains repeats
the comparisons of insert and answers whether it reached a node
with the value, and height is the length of the longest path to a
leaf.
The seven values are inserted in an order that balances the tree, so its height is 3 and the in-order walk prints them sorted. The search finds 40 and reports that 45 is absent, with three comparisons at most for either answer.
$ a68g tree.a68 3 20 30 40 50 60 70 80 T F
The shape of the tree
The height of a tree depends on the order of insertion, not only on the values it holds. Inserting sorted values makes every new node the right child of the previous one, so the tree becomes a chain, while a mixed order spreads the nodes over both subtrees.
MODE TREE = STRUCT (REF TREE left, right, INT value);
MODE BST = REF TREE;
BST empty tree = NIL;
PROC insert = (REF BST t, INT value) VOID:
IF t IS empty tree THEN
t := HEAP TREE := (empty tree, empty tree, value)
ELSE
IF value < value OF t THEN
insert(left OF t, value)
ELIF value > value OF t THEN
insert(right OF t, value)
FI
FI;
PROC height = (BST t) INT:
IF t IS empty tree THEN
0
ELSE
INT l = height(left OF t);
INT r = height(right OF t);
1 + IF l > r THEN l ELSE r FI
FI;
BEGIN
[1:7] INT sorted := (10, 20, 30, 40, 50, 60, 70);
[1:7] INT mixed := (40, 20, 60, 10, 30, 50, 70);
BST a := empty tree;
BST b := empty tree;
FOR i TO 7 DO
insert(a, sorted[i]);
insert(b, mixed[i])
OD;
print(("sorted input: height ", whole(height(a), 0), newline));
print(("mixed input: height ", whole(height(b), 0), newline))
END
A chain of seven nodes has height 7 and turns every search into a linear scan of the values. The balanced tree of the same values has height 3, which is the smallest possible for seven nodes, and each search needs at most three comparisons. A tree that is built from data that arrives in order therefore needs a balancing step to keep its advantage.
Both trees hold the same seven values and both walk in sorted order; only their shape differs. The numbers show the height of each, and the difference grows with the number of values: a chain of a thousand nodes is no better than a list.
$ a68g balance.a68 sorted input: height 7 mixed input: height 3
Which structure to use
A stack is the structure for anything that has to be undone in the reverse order: nested calls, an undo history, the pending work of a depth-first traversal. A queue keeps work in arrival order and is the natural home of a scheduler or a breadth-first traversal. A tree answers questions about order, such as the smallest value above a limit, which neither of the other two can do without a scan.
All three are built from the same pieces: a structure with references, nodes allocated on the heap, and procedures that take a reference when they change the structure. The linked lists article introduces those pieces, and recursion explains the walks over a tree.
Next steps
The linked lists article explains the nodes and references that all three structures use, and references and the heap covers the storage they live in. Recursion describes the tree walks, and searching compares the tree with the binary search over a sorted row.
Source
Revised Report on the Algorithmic Language Algol 68
In this article we have built a stack and a queue from references, written a binary search tree with insertion, traversal, search, and height, and seen how the order of insertion decides whether the tree is a fast index or a chain.
Author
List all Algol 68 tutorials.