The TAO of Java

Linear Structures

Summary: We consider the essential features of a class of abstract data types known as linear structures. Linear structures permit you to collect information and retrieve one piece of information at a time.

Contents:

• Introduction: Collections
• Linear Structures
• Additional Operations
• A Linear Structure Interface

Introduction: Collections

As you may have learned earlier, computer scientists regularly design, analyze, and implement mechanisms for collecting information. Why do we have more than one general Collection data type? Because it turns out that we can often make the implementation more efficient if we focus on certain operations. (More precisely, we can make the implementation of those operations more efficient if we focus on those operations.)

You have probably already encountered a variety of collections in your computer science, mathematics, or even real world education. For example, a set collects values and provides one central operation of membership. In contrast, a list, such as a list of students in a class, collects values and provides a central operation of visiting each value in the list in turn. Over the next few readings and labs, we will consider a variety of collections and their implementations.

Linear Structures

Among the simplest collections we encounter are the so-called linear structures. Linear structures are collections that let you add elements and will return elements to you one-by-one (removing the elements as they are returned). You can think of a to-do list or a job jar as kinds of linear structures: As you come up with new tasks, you add them to the list or jar. When you have time to undertake a new task, you grab one from the list or jar.

Linear structures therefore provide two central operations:

• put(T value), which adds an object to the structure.
• T get(), which removes and returns one object from the structure.

You may be asking yourself (or the page, or the computer screen, or your professor) what determines which object get() returns. In the most generic form of linear structure, the particular object returned by get is not specified. However, we do build a variety of kinds of linear structures, each with its own policy for specifying which object get returns.

• Stacks return objects using a last-in, first-out policy. That is, get removes and returns the object that has been most recently added to the stack.
• Queues return objects using a first-in, first-out policy. That is, get removes and returns the object that has been least recently added to the stack.
• Priority Queues return objects based on some ordering. In this case, the get operation removes and returns the object of highest priority. In Java, we typically specify the priority using the compareTo operation or a separate object that implements Comparator.
• Randomized Linear Structures return objects randomly. In this case, it should be difficult to predict which value the structure will return.

We will visit each of these structures over the next few readings and labs.

Additional Operations

So far, we've only specified two operations for linear structures. Are there others we might want or expect them to provide? Certainly.

One principle many designers employ is that any precondition that a client must meet must also have a mechanism for checking that precondition. Since it is a bad idea to try to get a value from an empty structure, clients probably need access to a isEmpty predicate.

Experience also suggests that there are times in which it is useful to check what value get will return, but not to remove that value. (Note that while we can remove and re-add the value in a stack or priority queue, if we remove an element and re-add it in a queue or a randomized linear structure, it moves to the end.) For such situations, many designers of linear structures include a peek operation.

Some designers prefer as much symmatry in their structures as they can provide. Others worry about implementation and note that we will eventually run out of room as we add values to a collection. Both classes of designers provide an isFull method. We will take the perspective that when we run out memory, something is seriously wrong with our program, and will not provide an explicit isFull.

Some designers like to add functionality by permitting clients to determine how many values are in the structure. Others note that determining the size of a linear structure is not central to the mission of linear stuctures and do without it. We follow the latter strategy.

You may also want to consider which of the standard object methods a linear structure should implement. Should we be able to convert the structure to a string and see all of the values? (If so, in what order should they appear?) What does it mean for two linear structures to be equals? Can we consider one linear structure naturally smaller than another?

A Linear Structure Interface

We have considered the primary purpose of linear structures (to collect values and then to extract them one at a time) and the key methods one provides for linear structures (put, get, isEmpty, and peek). We are now ready to put everything together into a Java interface that specifies the details.

/**
 * A simple collection of values that permits clients to add elements
 * and to extract them one-by-one.
 *
 * @author Samuel A. Rebelsky
 * @version 1.1 of March 2006
 */
public interface LinearStructure<T>
{
  /**
   * Add an element to the structure.  We assume that linear structures
   * never fill, and issue a significant error if the structure fills.
   * (The error is significant and rare enough that we do not list it 
   * as an exception, which means that programmers are not forced to 
   * catch it.)
   *
   * @param val
   *   The object that is to be added.
   * @post
   *   The collection now contains an additional copy of val.
   */
  public void put(T val);

  /**
   * Remove an element from the structure.  The particular policy
   * for removal is determined by the implementation or variant.
   *
   * @return val
   *   An object in the structure.
   * @pre
   *   The structure is not empty.
   * @post
   *   The structure contains one fewer copy of val.
   */
  public T get();

  /**
   * Determine which object will next be returned by get.
   *
   * @return val
   *   An object in the structure.
   * @pre
   *   The structure is not empty.
   * @post
   *   val is the same value that get() would return.
   *   The structure is unchanged.
   */
  public T peek();

  /**
   * Determine if the structure is empty.
   */
  public boolean isEmpty();

} // interface LinearStructure

History

Sunday, 6 March 2005 [Samuel A. Rebelsky]

• Created.

Tuesday, 7 March 2006 [Samuel A. Rebelsky]

• Updated to handle generics.
• Added a few other potential operations.