Abstract Data Types (ADTs), Stacks, and Queues: An Overview

An important theme that pervades much problem solving with computing involves the managing of complexity. Often computing applications seek to address problems and difficulties of people; computing offers the possibility of making a community a better place. However, when addressing societal challenges, the problems posed often are large and complex. In this context, a natural question is, "how can a programmer or a development team organize their work to handle complexity?"

In practice, the general field of software engineering provides insights and proposes approaches. A full study of software engineering requires extensive study and thus is far beyond the scope of this course. However, two related topics fit nicely within our current context: levels of abstraction and Abstract Data Types (ADTs).

Still another issue relates to how much data should we store in various structures. Also, to what extent should we store data once, referring to it (e.g., via pointers) elsewhere in a program, and to what extent should we make multiple copies of the data.

The notes that follow expand somewhat upon these three points. Discussion of levels of abstraction builds upon previous work throughout the course. Later work in this module explores ADTs and copies of data in additional depth.

Levels of Abstraction

One fundamental approach for managing complexity involves limiting the amount of detail that a developer must handle at one time. Various capabilities are organized into levels of abstraction, each drawing upon work developed at lower levels.

As an illustration, consider programming done within this course.

• At the lowest level, hardware performs various tasks, based on circuits, binary instructions, and data in binary form.

• The operating system works directly with the hardware to accomplish common tasks. Here are a few examples:

  • When one moves a mouse into a window and starts typing, the operating system recognizes which process or program is running in that window and passes the typed data to that process.
  • When opening a file to edit, the user indicates a file name, the operating system locates the relevant file and determines the details of how that file can be read.
  • When several windows are active, the operating system allocates processing time for the work in each of the windows.

  • When a program imports a library package, such as ArrayList or System.out, the programmer relies upon appropriate array-access and printing operations — the programmer does not need to focus on specific details in the ArrayList structure or writing process. (What really happens when a laser printer moves paper and places toner on a page to create images and text? Fortunately, such details are handled behind the scenes at a low level of abstraction, and the user need not devote time or effort to that work.)

• User programs utilize import statements to build upon previously-defined libraries. In some cases (e.g., with linked lists), a user may define separate libraries that can be used with multiple projects and programs.

With all of this work, software development can focus upon some elements of an overall application at a time. Once low-level capabilities are available, higher-level work can use the relevant functions and structures. No need to worry about various details at high levels, once the implementations are properly completed.

Overall, we can manage much complexity by dividing an overall project into largely-independent levels and then developing the capabilities of each level separately.

Abstract Data Types (ADTs)

Another approach for managing complexity involves grouping data together with the operations that process that data. Such a logical, operational unit is called an Abstract Data Type, abbreviated ADT. That is, an Abstract Data Type or ADT contains two parts:

• a conceptually-coherent collection of data, and
• the operations that work with that data.

Further, in describing an ADT, the user interface is considered as being separate from the implementation details. As an example, we might abstract the properties of a list as involving the creation of a list, insertion and deletion of elements, retrieval of one or more elements, and possible rearrangement or altering of elements. To define a ListADT, we would need to carefully describe the user's perspective in a header file, and then an implementation file would supply details.

From the standpoint of an ADT, the user interface identifies the logical data types and describes what the operations do. The specification of an ADT describes behavior — what is to be done, but not how.

A separate implementation file provides the working code behind the scenes. Sometimes, if processing seems slow with one implementation of an ADT, the behind-the-scenes details may change dramatically for efficiency. However, an application using the ADT could remain unchanged — utilizing a new implementation without changing the interface or application code in any way.

The readings and labs in this module describe two common ADTs: stacks and queues. In both cases, a header file specifies the data type and associated operations. Also, in both cases, we will explore one implementation involving an array behind the scenes, and another implementation involving linked lists. With either implementation, the user interface will be the same, but the coding details will be quite different.

To what extent should we copy data?

Throughout this module, we will be passing data into a new structure (a stack or a queue) and then retrieving the data in a particular way. Within this framework, we might store a reference to the original data in a new structure, or we could store a copy of the original data. Several arguments on each side are possible:

• Store a reference to the original data.

  • Storing a reference requires little space.
  • Storing a reference requires little time — new space need not be allocated, and time is not needed for copying.
  • Storage of references means that only one copy (the original) is saved. Changing the original therefore updates the data everywhere — no need to update multiple copies, and the data remain consistent.

• Store a copy of the data.

  • If the stored copy is changed, the original retains its old value — leaving a traceable record.
  • If the original is changed, the stored copy is available without adjustment.

The project at the end of this module reviews both of these approaches (storing references and storing copies) and explores examples illustrating various consequences.