Abstract Data Types

Most programming languages don’t come with the stack as a built-in data type or class. Instead, it’s up to you to implement it yourself. This is a stark contrast with arrays, which are available in most languages.

To create a stack, then, you generally have to use one of the built-in data structures to hold the data. Here’s one way to implement a stack using Python, which uses an array under the hood:

	class Stack:
	def __init__(self):
	self.data = []

	def push(self, element):
	self.data.append(element)

	def pop(self):
	if len(self.data) > 0:
	return self.data.pop()
	else:
	return None

	def read(self):
	if len(self.data) > 0:
	return self.data[-1]
	else:
	return None

As you can see, our stack implementation stores the data in an array called self.data.

Whenever a stack is initiated, we automatically build an empty array with self.data = []. Our stack also contains methods that push a new element onto the end of self.data, pop an element from the beginning of self.data, and read the first element from the self.data array. (The read and pop methods return None if the stack is empty.)

However, by building the Stack class around the array, we’ve built an interface that forces the user to interact with the array in limited ways. While one can normally read from any index of an array, when using the array through the stack interface, one can only read the last item. The same goes for inserting and deleting data.

The stack data structure, then, isn’t the same kind of data structure that an array is. The array is built into most programming languages and interacts directly with the computer’s memory. The stack, on the other hand, is a set of rules and processes around how we should interact with an array so that we can achieve a particular result.

In fact, a stack doesn’t even care about what data structure is under the hood. All it cares about is that there’s a list of data elements that act in a LIFO way. Whether we accomplish this with an array or some other type of built-in data structure doesn’t matter. Because of this, the stack is an example of what is known as an abstract data type—it’s a kind of data structure that is a set of theoretical rules that revolve around some other built-in data structure.

The set we encountered in Chapter 1, , is another example of an abstract data type. Some implementations of sets use arrays under the hood, while other implementations use hash tables. The set itself, though, is simply a theoretical concept: it’s a list of non-duplicated data elements.

Many of the data structures we’ll encounter in the remainder of this book are abstract data types—they’re pieces of code that are written on top of other built-in data structures.

It should be noted that even a built-in data structure can be an abstract data type. Even if a programming language does implement its own Stack class, it doesn’t change the fact that the stack data structure is still a concept that allows for various data structures to be used under the hood.