abstract data type

An abstract data type (ADT) describes what a collection promises to do, without saying how it does it. Think of an ATM. From the outside you know its contract: insert a card, enter a PIN, withdraw cash, check a balance. You do not know — and do not need to know — whether the cash is in a drum, a tray, or a robotic arm behind the wall. The interface is the promise; the machinery is hidden. An ADT is exactly this kind of promise for a collection of data: the operations it supports and what each one means.

For example, the Stack ADT promises just push, pop, and 'look at the top,' with the rule that the last thing in is the first thing out. The Queue ADT promises the opposite order, first in first out. A Map (or Dictionary) ADT promises to store key-to-value pairs and look a value up by its key. Crucially, none of these says how. A stack can be built from an array or from a linked list; a map can be a hash table or a balanced tree. The ADT is the behavior; the data structure is one machine that delivers it.

Why separate the two? Because it lets you reason about correctness using only the promise, then swap the underlying machine for a faster one without touching the code that uses it — as long as the new machine keeps the same promise. This is the core of good software design: program against the interface, not the implementation. When you read that a queue's enqueue is O(1), that is a claim about a particular implementation of the Queue ADT, not about the ADT itself.