10.4 Introduction to Abstract Data Types (ADT)

Main Content

What is an abstract data type (ADT)?

An abstract data type, or ADT, is a way of thinking about data by focusing on two things:

• the data itself
• the operations that can be done to that data

This means an ADT is not just a list of values. It also includes the allowed actions, such as adding an item, removing an item, or looking at an item.

For example, a stack is an ADT. It stores data, but it also has special operations such as push and pop. A queue is another ADT, with operations such as enqueue and dequeue. A linked list is also an ADT because it stores data in linked nodes and allows items to be added or removed by changing pointers.

The word abstract means we are mostly interested in what the structure does, not all the low-level details of how it is built. In this topic, though, you also need to understand a simple way these ADTs can be implemented using arrays.

Main features of a stack

A stack has these important features:

• data is added and removed from one end only
• that end is called the top
• the most recently added item is the first one to come out
• a top pointer is often used to show the current top item
• if the stack is empty, the pointer shows there are no valid items
• if the stack is full and another item is added, this causes overflow
• if the stack is empty and an item is removed, this causes underflow

Editing data in a stack

The syllabus says you should be able to add, edit and delete data. In a stack:

• add means push a new item onto the top
• delete means pop the top item
• edit usually means changing a value that is already stored

In practice, a stack mainly allows direct work at the top. So if you want to change an item lower down, it is less convenient than using some other structure. That is one reason a stack is best when you mainly need to work with the most recent item.