Interfaces

In this lesson, we look at the operations supported by the most commonly used data structures. Anyone with a bit of programming experience can see that these operations are not hard to implement correctly. It should be considered required reading.

When discussing data structures, it is important to understand the difference between a data structure’s interface and its implementation. An interface describes what a data structure does, while an implementation describes how the data structure does it.

Interface versus implementation

An interface, sometimes also called an abstract data type, defines the set of operations supported by a data structure and the semantics, or meaning, of those operations. An interface tells us nothing about how the data structure implements these operations; it only provides a list of supported operations along with specifications about what types of arguments each operation accepts and the value returned by each operation.

A data structure implementation, on the other hand, includes the internal representation of the data structure as well as the definitions of the algorithms that implement the operations supported by the data structure. Thus, there can be many implementations of a single interface. For example, we can implement List interface using arrays and we can also implement it using pointer-based data structures. Each implements the same interface, List, but in different ways.

The Queue, Stack, and Deque interfaces

The Queue interface represents a collection of elements to which we can add elements and remove the next element. More precisely, the operations supported by the Queue interface are:

• add(x): It adds the value x to the Queue.
• remove(): It removes the next (previously added) value, y, from the Queue and return y.

Note: The remove() operation takes no argument. The Queue’s queueing discipline decides which element should be removed.

There are many possible queueing disciplines, the most common of which include FIFO, priority, and LIFO.

A FIFO (first-in-first-out) Queue, which is illustrated below, removes items in the same order they were added, much in the same way a queue (or line-up) works when checking out at a cash register in a grocery store. This is the most common Queue so the qualifier FIFO is often omitted. In other texts, the add(x) and remove() operations on a FIFO Queue are often called enqueue(x) and dequeue(), respectively.

A priority Queue, illustrated below, always removes the smallest element from the Queue, breaking ties arbitrarily. This is similar to the way in which patients are triaged in a hospital emergency room. As patients arrive they are evaluated and then placed in a waiting room. When a doctor becomes available he or she first treats the patient with the most life-threatening condition. The remove() operation on a priority Queue is usually called deleteMin() in other texts.

A very common queueing discipline is the LIFO (last-in-first-out) discipline, illustrated below. In a LIFO Queue, the most recently added element is the next one removed. This is best visualized in terms of a stack of plates; plates are placed on the top of the stack and also removed from the top of the stack. This structure is so common that it gets its own name: Stack. Often, when discussing a Stack, the names of add(x) and remove() are changed to push(x) and pop(); this is to avoid confusing the LIFO and FIFO queueing disciplines.

A Deque is a generalization of both the FIFO Queue and LIFO Queue (Stack). A Deque represents a sequence of elements, with a front and a back. Elements can be added at the front of the sequence or the back of the sequence. The names of the Deque operations are self-explanatory: addFirst(x), removeFirst(), addLast(x), and removeLast(). It is worth noting that a Stack can be implemented using only addFirst(x) and removeFirst() while a FIFO Queue can be implemented using addLast(x) and removeFirst().

The List interface: linear sequences

This course will talk very little about the FIFO Queue, Stack, or Deque interfaces. This is because these interfaces are subsumed by the List interface. A List, illustrated below, represents a sequence, $x_0,...,x_{n−1},$ of values.

In the above list, a call to get(2) would return the value c.

The List interface includes the following operations:

• size(): It returns n, the length of the list.
• get(i): It returns the value $x_i$.
• set(i, x): It sets the value of $x_i$ equal to $x$.
• add(i, x): It adds $x$ at position $i$, displacing $x_i,...,x_{n−1}$;
  • Set $x_{j + 1} = x_j$ , for all $j ∈ \{n − 1, . . . , i\}$, increment $n$, and set $x_i = x$.
• remove(i): It removes the value $x_i$, displacing $x_{i+1},...,x_{n−1}$;
  • Set $x_j = x_{j + 1}$, for all $j ∈ \{i,...,n−2\}$ and decrement $n$.

Notice that these operations are easily sufficient to implement the Deque interface:

$$\begin{split} \text{addFirst}(x) & => \text{add}(0,x) \\ \text{removeFirst}() & => \text{remove}(0) \\ \text{addLast}(x) & => \text{add}(\text{size},x) \\ \text{removeLast}() & => \text{remove}(\text{size}()-1) \end{split}$$

The terms Stack and Deque are sometimes used in the names of data structures that implement the List interface. When this happens, it highlights the fact that these data structures can be used to implement the Stack or Deque interface very efficiently. For example, the ArrayDeque class is an implementation of the List interface that implements all the Deque operations in constant time per operation.

The USet interface: unordered sets

The USet interface represents an unordered set of unique elements, which mimics a mathematical set. A USet contains $n$ distinct elements; no element appears more than once; the elements are in no specific order. A USet supports the following operations:

• size(): It returns the number, $n$, of elements in the set.
• add(x): It adds the element $x$ to the set if not already present. It adds $x$ to the set provided that there is no element $y$ in the set such that $x$ equals $y$. It returns true if $x$ was added to the set and false otherwise.
• remove(x): It removes $x$ from the set; Find an element $y$ in the set such that $x$ equals $y$ and remove $y$. Return $y$, or null if no such element exists.
• find(x): It finds $x$ in the set if it exists. It finds an element $y$ in the set such that $y$ equals $x$. Return $y$, or null if no such element exists.

These definitions are a bit fussy about distinguishing $x$, the element we are removing or finding, from $y$, the element we may remove or find. This is because $x$ and $y$ might actually be distinct objects that are nevertheless treated as equal. Such a distinction is useful because it allows for the creation of dictionaries or maps that map keys onto values.

To create a dictionary/map, one forms compound objects called Pairs, each of which contains a key and a value. Two Pairs are treated as equal if their keys are equal. If we store some pair $(k,v)$ in a USet and then later call the find(x) method using the pair $x = (k, \text{null})$ the result will be $y = (k, v)$. In other words, it is possible to recover the value, $v$, given only the key, $k$.

The SSet interface: sorted sets

The SSet interface represents a sorted set of elements. An SSet stores elements from some total order, so that any two elements $x$ and $y$ can be compared. In code examples, this will be done with a method called compare(x,y) in which

$$\text{compare}(x,y) \begin{cases} < 0 & \text{if $x < y$}\\ > 0 & \text{if $x > y$}\\ = 0 & \text{if $x = y$}\\ \end{cases}$$

The above equation explains:

• If $x < y$, then the resulting value is negative.
• If $x > y$, then the resulting value is positive.
• If $x = y$, then the resulting value is 0.

An SSet supports the size(), add(x), and remove(x) methods with exactly the same semantics as in the USet interface. The difference between a USet and an SSet is in the find(x) method:

• find(x): It locates $x$ in the sorted set; Find the smallest element $y$ in the set such that $y \ge x$. Return $y$ or null if no such element exists.

This version of the find(x) operation is sometimes referred to as a successor search. It differs in a fundamental way from USet.find(x) since it returns a meaningful result even when there is no element equal to $x$ in the set.

The distinction between the USet and SSet find(x) operations is very important and often missed. The extra functionality provided by an SSet usually comes with a price that includes both a larger running time and a higher implementation complexity. For example, the implementation of find(x) operations in SSet has a running time that is logarithmic in the size of the set. On the other hand, the implementation of find(x) operation in USet has a constant expected running time.