- Take the goat across the river and return with no passengers
- Take the cabbage across the river and return with the goat
- Take the wolf across the river and return with no passengers
- Take the goat across the river
The sequence is one of the three basic logic structures in computer programming.
The other two logic structures are selection and loop.
In a sequence structure, an action or event leads to the next ordered action in a predetermined order.
The sequence can contain any number of actions, but no actions can be skipped in the sequence.
The program, when run, must perform each action in order with no possibility of skipping an action or branching off to another action.
The most important distinction between elementary structured types and types of advanced structure is that in the former case the cardinality of the
type is strictly finite, provided that the cardinality of the constituent types is. The distinction between a finite and an infinite set is one of profound mathematical significance, and it has many consequences relating to methods of
representation and manipulation.
(1) Since the number of potential values of the type may be infinite, the amount of storage allocated to hold a value of an advanced structure is not determinable from the declaration itself. It is normally only determined when the program is actually running, and in many cases, varies during the execution of the program. In the case of an elementary structure, the number of different potential values is finite, and the maximum amount of storage
required to hold any value is fixed and determinable from the form of the declaration.
(2) When the size of a structured value is fairly large, it is more efficient to update individual components of the structure separately, rather than to assign a fresh value to the entire structure. Even for elementary types, it has been found sometimes more efficient to perform selective updating, particularly for unpacked representations of Cartesian products and for arrays.
The increased efficiency of selective updating is usually even more pronounced in the case of advanced data structures.
(3) Advanced data structures, whose size varies dynamically, require some scheme of dynamic storage allocation and relinquishment. The units of storage which are required are usually linked together by pointers, sometimes known as references or addresses; and their release is accomplished either by explicitly programmed operations, or by some form of general garbage collection. The use of dynamic storage allocation and pointers leads to a
significant complexity of processing, and the problems can be particularly severe when the data has to be transferred between the main and backing store of a computer. No problems of this kind need arise in the case of
elementary data structures.
(4) The choice of a suitable representation for an advanced data structure is often far more difficult than for an elementary structure; the efficiency of the various primitive operations depends critically on the choice of representation,
and therefore a sensible choice of representation requires a knowledge of the relative frequency with which these operations will be invoked. This knowledge is especially important when a part or all of the structure is held on a backing store; and in this case, the choice of repreisentation should take into account the characteristics of the hardware device; that is, arrangement of tracks and cylinders on a rotating medium, and times
of head movement and rotational delay. In the case of elementary structures, the primitive operations are of roughly comparable efficiency for most
Advanced and Elementary Structures
Thus the differences between advanced and elementary structures are quite pronounced, and the problems involved are significantly greater in the advanced case. This suggests that the practical programmer would be well advised to confine himself to the use of elementary structures wherever possible, and to resort to the use of advanced structures only when the nature of his application forces him to do so.
The first and most familiar example of an advanced data structure is the sequence. This is regarded as nothing but a sequence of an arbitrary number of items of some given type. The use of the term "sequence" is intended to cover sequences on magnetic tapes, disc, or drum, or in the main store. Sequences in the main store have sometimes been known as streams, lists, strings, stacks, deques, queues, or even sets. The term file (or sequential
file) is often used for sequences held on backing store. The concept of a sequence is an abstraction, and all these structures may be regarded as its various representations.