This section shows how to use pairs to represent a data structure called a queue. Section will show how to represent data structures called tables.
Figure shows an initially empty queue in which the items a and b are inserted.
Then a is removed, c and d are inserted, and b is removed. However, this representation is inefficient, because in order to insert an item we must scan the list until we reach the end. Since the only method we have for scanning a list is by successive cdr operations, this scanning requires steps for a list of n items. The difficulty with the list representation arises from the need to scan to find the end of the list. The reason we need to scan is that, although the standard way of representing a list as a chain of pairs readily provides us with a pointer to the beginning of the list, it gives us no easily accessible pointer to the end.