Data Abstraction and Encapsulation

Classes normally hide the details of their implementation from their clients. This is called information hiding. As an example, let us consider the stack data structure introduced in Section 7.6. Recall that a stack is a last-in, first-out (LIFO) data structurethe last item pushed (inserted) on the stack is the first item popped (removed) off the stack.

Stacks can be implemented with arrays and with other data structures, such as linked lists. (We discuss stacks and linked lists in Chapter 25, Data Structures, and Chapter 27, Collections.) A client of a stack class need not be concerned with the stack's implementation. The client knows only that when data items are placed in the stack, they will be recalled in last-in, first-out order. The client cares about what functionality a stack offers, not about how that functionality is implemented. This concept is referred to as data abstraction. Although programmers might know the details of a class's implementation, they should not write code that depends on these details. This enables a particular class (such as one that implements a stack and its push and pop operations) to be replaced with another version without affecting the rest of the system. As long as the public services of the class do not change (i.e., every original method still has the same name, return type and parameter list in the new class declaration), the rest of the system is not affected.

Most programming languages emphasize actions. In these languages, data exists to support the actions that applications must take. Data is "less interesting" than actions. Data is "crude." Only a few simple types exist, and it is difficult for programmers to create their own types. C# and the object-oriented style of programming elevate the importance of data. The primary activities of object-oriented programming in C# are the creation of types (e.g., classes) and the expression of the interactions among objects of those types. To create languages that emphasize data, the programming-languages community needed to formalize some notions about data. The formalization we consider here is the notion of abstract data types (ADTs), which improve the application-development process.

Consider simple type int, which most people would associate with an integer in mathematics. Actually, an int is an abstract representation of an integer. Unlike mathematical integers, computer ints are fixed in size. For example, simple type int in C# is limited to the range 2,147,483,648 to +2,147,483,647. If the result of a calculation falls outside this range, an error occurs, and the computer responds in some manner. It might, for example, "quietly" produce an incorrect result, such as a value too large to fit in an int variablecommonly called arithmetic overflow. It also might throw an exception, called an OverflowException. (We discuss the two ways of dealing with arithmetic overflow in Section 12.8.) Mathematical integers do not have this problem. Therefore, the computer int is only an approximation of the real-world integer. The same is true of double and other simple types.

We have taken the notion of int for granted until this point, but we now consider it from a new perspective. Types like int, double, and char are all examples of abstract data types. They are representations of real-world concepts to some satisfactory level of precision within a computer system.

An ADT actually captures two notions: a data representation and the operations that can be performed on that data. For example, in C#, an int contains an integer value (data) and provides addition, subtraction, multiplication, division and remainder operationsdivision by zero is undefined. C# programmers use classes to implement abstract data types.

Another abstract data type we discuss is a queue, which is similar to a "waiting line." Computer systems use many queues internally. A queue offers well-understood behavior to its clients: Clients place items in a queue one at a time via an enqueue operation, then get them back one at a time via a dequeue operation. A queue returns items in first-in, firstout (FIFO) order, which means that the first item inserted in a queue is the first item removed from the queue. Conceptually, a queue can become infinitely long, but real queues are finite.

The queue hides an internal data representation that keeps track of the items currently waiting in line, and it offers operations to its clients (enqueue and dequeue). The clients are not concerned about the implementation of the queuethey simply depend on the queue to operate "as advertised." When a client enqueues an item, the queue should accept that item and place it in some kind of internal FIFO data structure. Similarly, when the client wants the next item from the front of the queue, the queue should remove the item from its internal representation and deliver it in FIFO order (i.e., the item that has been in the queue the longest should be returned by the next dequeue operation).

The queue ADT guarantees the integrity of its internal data structure. Clients cannot manipulate this data structure directlyonly the queue ADT has access to its internal data. Clients are able to perform only allowable operations on the data representationthe ADT rejects operations that its public interface does not provide. We will discuss stacks and queues in greater depth in Chapter 25, Data Structures.