Abstract data types express an idea about how to store and retrieve data, and data structures are the classes that implement abstract data types. Separating the idea from its code allows you to talk about expected behavior without needing to understand the implementation. Learn more about how and why software engineers use abstract data types in this video.
- [Instructor] Before we dive into stacks, ques and decks we should understand more about what abstract data types are. Abstract data types are a theoretical computer science concept. They simply describe what kind of data a data structure can hold and what operations are allowed on that data. If you were creating an entirely new abstract data type from scratch you could decide what these operations would be but since we're working with stacks, ques and decks, which are already defined and understood in the computer science community we'll stick to the basic operations that already exist for those abstract data types.
When we think about the purpose of an abstract data type we're not at all concerned with how we'd code it we just want to understand how we should be able to interact with it in the way we'll need to. Again an abstract data type just expresses an idea. Abstract data types aren't specific to a certain programming language. You could implement one in many different languages. Abstract data types are always talked about from the perspective of the person who will be using them, not from the perspective of the person who is going to implement it.
There are two styles for spelling out how an abstract data type works, the imperative style and the functional style. In the imperative definition of an abstract data type we think of the abstract data type as mutable or changeable. We allow the same abstract data type to be in different states at different times. Since operations on the abstract data type can change its state the order in which those operations are executed is important. This is the style we'll be using throughout our course.
The other style is called the functional style. In the functional definition of an abstract data type we think of the abstract data type as immutable or not changeable. It has a separate entity of the abstract data type for each state that it can be in. This means that an operation that modifies the abstract data type is operating on the present state and returning and entirely new state as a result. And this way the original abstract data type is never changed. Consequently the order in which the operations are executed in the functional definition doesn't matter since no operation is changing the present state.
There are a couple advantages to thinking about data using an abstract data type. The first is abstraction. Regardless of how the abstract data type is implemented to eventually become a data structure the abstract data type will have certain predictable properties and allowed operations that we specify at the outset. All a user of the abstract data type needs to know is the type of data it requires and the allowed operations on it. An understanding of the implementation is not necessary in order for the user to make use of the resulting data structure.
The second advantage is consistency. A person who is using the interface of a data structure as specified by it's abstract data type doesn't need to understand the implementation. Consequently the implementation of that data structure could change and as long as the new implementation supports the existing interface the user doesn't need to change their own code. The next thing we need to understand is data structures.
- Abstract types and data structures
- Stacks as a linear abstract data type
- Creating the Stack class and its methods
- Adding items to the top and bottom of a stack
- Creating the Queue class and its methods
- Manipulating items in a queue
- Creating the Dequeue class and its methods
- Adding and removing items from a dequeue