Топик: Organizing information

15.In spite of the American origins of many ideas associated with computers, that great British institution, the queue, has found its way into the theory o computing. Everyone knows how a queue works: newcomers join at the rear, service is provided at the front, and no pushing-in is allowed. Exactly the same rules apply to queues of data stored in a computer memory^ data items are added at the back and removed from the front. A queue is a first-in-first-out (FIFO) data structure.

16.Although queues are used slightly less frequently than stacks, they do have a variety of applications. These include queuing data items in transit between a processor and a peripheral device, or at intermediate points in a data communications network.

4. Lists

A list is a set of data items stored in some order. Data items may be inserted or deleted at any point in the list. In this respect, a list is less restrictive than a stack or queue. The simplest way of implementing a list makes use of a pointer from each item to the one following it in the list. There is also a pointer to the start of the list, while the last item it the list has a null pointer. See Figure 5.

A data structure of this type is also known as a linked link. A list element consists of a data item and its pointer. In many applications a list element contains a number of data items. Since elements can easily be added to the rear or removed from the front of the linked list, this structure my also be used to implement a queue. Inserting an element into a list is achieved by adjusting the pointers to include the new element. See Figure 6. Removing an element is achieved in a similar way, as shown in Figure 7.

Data items in a lust are in order, in the sense that one data item is behind another in the list. Lists are, however, frequently used in cases where the data items are in numerical or alphabetical order. Such lists are called ordered lists. Lists are very useful for storing ordered sets of data, if insertions and deletions of data items are frequent.

Data items may themselves be entire lists. Lists of this nature are widely used in artificial intelligence research, and form the basis of the programming language Lisp.

5. Trees

We are all familiar with phrases “family tree” and “getting to the top of the tree”. In this sense, a tree is a structure implying a hierarchy, with each element of the tree being linked to elements below it. For example, the tree in Figure 7 shows the descendants of Queen Elizabeth II.

Each data item in a tree is at a node of the tree. The node at the top of the tree is called the root. Each node may be connected to one or more subtrees, which also have a tree structure. A node at the bottom the tree, which has no subtrees, is called a terminal node, or a leaf. See Figure 9.

A number of operations may be carried out on trees. Two binary trees may be joined to en additional node, which becomes the root a larger binary tree, with the original trees as subtrees. A tree may be traversed in several ways. Traversing a tree is accessing its elements in a systematic way. See Figure 10.

Tress Have a number of applications in computing. The modules of many programs are linked together in a tree structure. Trees are also used to represent arithmetic expressions, and for sorting and searching. Some computers regard their entire memory as if it were partitioned into a tree structure.

The essential feature of a tree is that each node is connected to subtrees, which themselves have the structure of trees. In other words, wherever you are in a tree, the structure “below” you is a tree. In this sense a tree is a recursive data structure, and can be manipulated by recursive programs. This is the property of tree which makes them so useful from a computing point of view.

A number of program languages require that the type of each data item be declared before the data item is used in a program. A data item may be an integer, an array, or a list, to name just a few examples.