In the last chapter, we saw a few basic data structures and some algorithms to manipulate them. However, sometimes we may want to hide the implementation details of a data structure and only want to know how they interact with other algorithms. We may want to specify a few operations that they must allow and forget about how they are achieved. This is not very different from abstraction of a part of a program in any large software application. For example, in Java, we create interfaces that only define the methods of an object that its class must implement, and then we use this interface type, being confident that they will be implemented properly. We do not want to think about how an implementation class would provide their implementation. Such interfaces of data structure are called abstract data types. To put this another way, an abstract data type (ADT) is a description of what a data structure should do for its user. It is a list of operations...