COMPUTING SCIENCE

# Trains of Thought

Computing with locomotives and box cars takes a one-track mind

Tracking Data

Sidings, wyes and other devices for directing trains inspired some of the earliest ideas about managing the flow of information through a computer program. In 1961 Edsger W. Dijkstra included a diagram of a railroad wye in a memorandum about methods of translating the new programming language Algol 60. In parsing an expression such as 3x(5+2), the seven symbols are read from left to right, but they must be acted on in a different order: First the subexpression inside the parentheses is evaluated by adding 5 and 2, then the result of this operation is multiplied by 3. Dijkstra showed that the reordering can be accomplished by temporarily storing the operators (such as x and +) in a data structure called a stack. The stack is a first-in, last-out storage device; in this case the x sign goes in first, followed by the + sign, but they come out in the opposite order. Dijkstra chose to explain this principle in terms of a railroad wye. One of the three tracks serves as input, one as output, and the third provides the first-in, last-out storage.

A few years later Donald E. Knuth, in the first volume of *The
Art of Computer Programming*, gave railroading
interpretations of three important data structures: the stack, the
queue and the double-ended queue, or deque. The queue is the
simplest of these—at least for railroaders. A queue is a
first-in, first-out data structure, and so it is represented by a
simple straight length of track. Cars put in at one end of the queue
come out the other end in the same order. A deque is an arrangement
of tracks allowing cars to be added at either end and removed from
either end (but there is no access to cars in the middle of the
train). Knuth illustrates a deque by a complicated layout of two
back-to-back jug-handle loops, requiring four switches. The same
functions can also be accomplished by an ordinary siding, provided
that trains are allowed to back up in order to pass through a
trailing-point switch. (The siding and the double-jug-handle layouts
differ in their effect on the orientation of the cars.)

EMAIL TO A FRIEND :

**Of Possible Interest**

**Letters to the Editors**: Traffic Lights Near and Far

**Engineering**: Traffic Signals, Dilemma Zones, and Red-Light Cameras

**Engineering**: From Lowly Paper Clips to Towering Suspension Bridges