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.

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, in teh Array-Based Lists section we see implementations of the List interface using arrays and in the Linked Lists section we see implementations of the List interface using pointer-based data structures. Each implementation uses the same interface but in different ways.

The Queue interface reperesents 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): add the value x to the Queue
• remove(): remove the next (previously added) value, y, frome the Queue and return y

Note that 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 includes FIFO, priority, and LIFO.

A FIFO (first-in-first-out) queue, illustrated in Fig.1, removes items in the same order they were added, much in the same way a queue works in a shop. This is the most common form of queue so the qualifier FIFO is often omitted. In other places you might find that the add(x) and remove() operations are instead called enqueue(x) and dequeue(x).

Fig.1: a FIFO queue

A priority queue, illustrated Fig.2, always removes the smallest element from the queue, breaking ties arbitrarily. This is similar to triage in A&E, where patients are evaluated on arrival and then placed in a waiting room to be seen by a doctor based on the severity of their condition. The remove() operation on a priority queue can often be called deleteMin().

Fig.2: A priority queue

LIFO (last-in-first-out) is a common queueing discipline, illustrated in Fig.3. In a LIFO Queue, the most recently added element is the next one removed. This structure is so common it is know by it's own name; Stack. This is because it acts much like a stack of items, with the last item added to the stack needing to be removed before each subsequent item (think plates or chairs). Often, when discussin a Stack, the names of add(x) and remove() are changed to push(x) and pop().

Fig.3: A stack.

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

The other sections won't cover these previous interfaces much. This is because they are encompassed by the List interface. A List, illustrated in Fig.4, represents a sequence, x₀,...,x_n-1, of values. The List interface includes the following operations:

1. size(): return n, the length of the list
2. get(i): return the value x_i
3. set(i,x): set the value of x_i equal to x
4. add(i,x): add x at postion i, displacing x₀,...,x_n-1;

Set x_j+1, for all j∈{n-1,...,i}, increment n, and set x_i = x

5. remove(i): remove the value x_i, displacing x_i+1,...,x_n-1;

Set x_j = x_j+1 for all j∈{i,...,n-2} and decrment n

Note that these operations are sufficient to implement the Deque interface:

Fig.4: A List represents a sequence indexed by 0,1,2,...,n-1.

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

Despite not discussing the FIFO queue, Deque and Stack interfaces in the analysis sections, the terms Stack and Deque are sometimes used in the names of data structures that implement the List interface. This simply highlights the fact that these data structures can be used to implement the Stack or Deque interface efficiently. An example of this is the ArrayDeque class which implements the List interface in a way that implements all the Deque operations in constant time per operation.

The USet interface is used to represent an unordered set of unique elements, which mimics a mathematical set. I.e. it contains n distinct elements (no element appears more than once), and the elements are in no specific order. A USet supports the following operations:

1. size(): return the number, n, of elements in the set
2. add(x): add the element x to the set if not already present;

Add x to the set provided that there is no element y in that set such that x = y. Return true if x was added and false if not.

3. remove(x): remove x from the set;

Find element y in the set such that x=y and remove y. Return y, or null (if y does not exist)

4. find(x): find x in the set if it exists

These are very particular definitions that differentiate x (the element to be found or removed), from y, (the element we may find or remove). This is because x and y could be distinct objects that are treated as equal (by overriding the Object's equals(y) and hashCode() methods.) This differentiation is useful in that it allows for the creation of key-value dictionaries(obsolete) or maps.

To create a map, we form compound objects, Pairs, each of which contain a key and a value. Two pairs are treated as equal if their keys are equal. So, we can recover the value, v, given only the key, k. For example, if we store some pair (k,v) in a USet and then later call the find(x) method using the pair x = (k,null) the result will be y = (k,v).

The SSEt interface represents a sorted set of elements. It stores the elements from some total order, so that any two elements, x and y, can be compared. This is done by using the compare(x,y) method where

An SSet supports the size(), add(x), and remove(x) methods in the same way USet does. The difference is in the find(x) method:

• find(x): locate x in the sorted set;

Fnd the smallest element, y, in the set such that y≥x. Return y or null(if no such element exists).

This versoin of the find(x) operation is sometimes referred to as a successor search (usually in reference to BST). It is fundamentally distinguishable from USet.find(x) in that it returns a meaningful result even if 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, most of the SSet implementations discussed in this wiki all have find(x) operations with running times that are logarithmic in the size of the set. On the other hand, the implementation of a USet as a ChainedHashTable has a find(x) operation that runs in constant expected time. When choosing which of these structures to use, we should always use a USet unless the extra functionality offered by an SSet is truly needed.