Abstract Data Types (ADT) Explained

In programming, we often talk about data structures, like arrays, lists, stacks, queues and so on.
But underneath them lies a deeper, more theoretical concept that defines how we use and reason about these structures: the Abstract Data Type, or ADT.

1. What is an Abstract Data Type (ADT)?

An Abstract Data Type (ADT) is a mathematical model that defines:

• What operations can be performed on a data structure.
• What behavior those operations guarantee, but not how they are implemented.

Think of it as a contract or a blueprint.

ADT

Logical description of data + allowed operations.

Tips

The “abstract” part means we don’t care about how it’s implemented internally — only about what it can do.

2. Everyday Analogy

Consider a vending machine.

• You can insert coins.
• You can select a product.
• You can get your product.

You don't need to know:

• What sensors are used,
• How the internal mechanism works,
• How it keeps track of inventory,
• How the machine counts your money,
• How it releases the drink.

Info

You just trust the interface. The what, not the how.

That’s exactly what an ADT is in computer science.

3. Formal Definition

An Abstract Data Type is defined by:

1. A set of values (the data it can store), and
2. A set of operations that can be performed on those values,
   along with rules that describe how those operations behave.

Example

A Stack ADT is defined by:

• Values: an ordered collection of elements.
• Operations:
  • push(x) — adds element x to the top,
  • pop() — removes the top element,
  • top() — looks at the top without removing,
  • is_empty() — checks if the stack is empty.

Warning

Nowhere do we say how the stack is implemented. It could be:

• An array,
• A linked list,
• A dynamic container.

Tips

The behavior stays the same. That’s the essence of abstraction.

4. ADT vs Data Structure

This is a classic confusion — and an important one to clear up:

Concept	Focus	Example	Description
Abstract Data Type (ADT)	What it does	Stack, Queue, Map	Defines operations and expected behavior.
Data Structure	How it works	Array, Linked List, Hash Table	Concrete way to store and organize data.

In other words:

• ADT = concept / behavior
• Data structure = implementation

You can implement the same ADT using different data structures.

Example

The Stack ADT can be implemented with:

• An array (fixed or dynamic size), or
• A linked list (nodes pointing to the next element).

Both support push and pop operations, but performance characteristics differ.

5. ADTs in Modern Programming

In modern languages, ADTs are often represented as interfaces, abstract classes, or concepts.

For example, in C++:

#pragma once

#include <optional>

// Data Structures namespace
namespace ds
{

template <typename T>
struct IStack
{
    virtual ~IStack() = default;

    /**
     * @brief Pushes a value onto the stack.
     */
    virtual void push(const T& v) = 0;

    /**
     * @brief Pops the top value off the stack and returns it.
     * @throws std::runtime_error if the stack is empty.
     */
    virtual void push(T&& v) = 0;

    /**
     * @brief Pops the top value off the stack and returns it.
     * @throws std::runtime_error if the stack is empty.
     */
    [[nodiscard]] virtual T pop() = 0;

    /**
     * @brief Checks if the stack is empty.
     * @return true if the stack is empty, false otherwise.
     */
    [[nodiscard]] virtual bool is_empty() const noexcept = 0;

    /**
     * @brief Constructs and pushes a value onto the stack.
     */
    template <typename... Args>
    void emplace(Args&&... args)
        requires std::constructible_from<T, Args...>
    {
        push(T(std::forward<Args>(args)...));
    }

    /**
     * @brief Tries to pop the top value off the stack.
     * @return std::optional containing the popped value, or std::nullopt if the
     * stack is empty.
     */
    [[nodiscard]] std::optional<T> try_pop()
    {
        if (is_empty())
        {
            return std::nullopt;
        }
        return pop();
    }
};

}  // namespace ds

This defines a Stack ADT. Any class implementing this interface provides a concrete data structure that fulfills the same behavioral contract. C++ interface is extended by additional operations like emplace and try_pop to enhance usability and performance.

6. Example: Stack ADT Implementations

Array-Based Stack (fixed capacity)

#pragma once

#include "IStack.hpp"

#include <array>
#include <cstddef>
#include <stdexcept>
#include <utility>

namespace ds
{

template <typename T, std::size_t Capacity>
class StackArray final : public IStack<T>
{
public:
    static_assert(Capacity > 0, "StackArray capacity must be greater than zero");

    void push(const T& v) override
    {
        push_impl(v);
    }
    void push(T&& v) override
    {
        push_impl(std::move(v));
    }

    [[nodiscard]] virtual T pop() override
    {
        ensure_not_empty();
        --top_index_;
        return std::move(data_[top_index_]);
    }

    [[nodiscard]] virtual bool is_empty() const noexcept override
    {
        return top_index_ == 0;
    }

private:
    template <class U>
    void push_impl(U&& v)
    {
        ensure_space();
        data_[top_index_] = std::forward<U>(v);
        ++top_index_;
    }

    void ensure_space()
    {
        if (top_index_ >= Capacity)
        {
            throw std::runtime_error("StackArray::push: capacity exceeded");
        }
    }

    void ensure_not_empty()
    {
        if (is_empty())
        {
            throw std::runtime_error("StackArray::pop: stack is empty");
        }
    }

    std::array<T, Capacity> data_{};
    std::size_t top_index_{0};
};

}  // namespace ds

Usage Example

#include "ds/StackArray.hpp"

#include <gtest/gtest.h>

using ds::StackArray;

TEST(StackArray, PushPopBasic)
{
    // Arrange
    StackArray<int, 4> s;
    EXPECT_TRUE(s.is_empty());

    s.push(1);
    s.push(2);

    EXPECT_FALSE(s.is_empty());
    EXPECT_EQ(s.pop(), 2);
    EXPECT_EQ(s.pop(), 1);
    EXPECT_TRUE(s.is_empty());
}

TEST(StackArray, EmplaceAndTryPop)
{
    StackArray<std::string, 3> s;

    s.emplace(3, 'x');  // "xxx"
    auto v = s.try_pop();

    ASSERT_TRUE(v.has_value());
    EXPECT_EQ(*v, "xxx");
    EXPECT_FALSE(s.try_pop().has_value());
}

TEST(StackArray, OverflowThrows)
{
    StackArray<int, 2> s;

    s.push(10);
    s.push(20);

    EXPECT_THROW(s.push(30), std::runtime_error);
}

TEST(StackArray, UnderflowThrows)
{
    StackArray<int, 1> s;
    EXPECT_THROW((void) s.pop(), std::runtime_error);
}

TEST(StackArray, PushByReference)
{
    StackArray<std::string, 2> s;
    std::string str = "hello";

    s.push(str);
    str = "world";
    s.push(std::move(str));

    EXPECT_EQ(s.pop(), "world");
    EXPECT_EQ(s.pop(), "hello");
}

// Covers capacity=1 successful push/pop path (previously only underflow was tested)
TEST(StackArray, CapacityOneHappyPath)
{
    StackArray<int, 1> s;
    EXPECT_TRUE(s.is_empty());

    int x = 42;
    s.push(x);  // cover const& overload for int, Capacity=1

    EXPECT_FALSE(s.is_empty());
    EXPECT_EQ(s.pop(), 42);  // cover pop success for Capacity=1 instantiation
    EXPECT_TRUE(s.is_empty());
}

// Ensure const& overload is exercised for int with capacity > 1
TEST(StackArray, IntLvaluePush)
{
    StackArray<int, 4> s;

    int a = 7;
    int b = 9;
    s.push(a);  // const& overload
    s.push(b);  // const& overload

    EXPECT_EQ(s.pop(), 9);
    EXPECT_EQ(s.pop(), 7);
}

// Exercise IStack<int>::try_pop both branches (value and nullopt)
TEST(StackArray, TryPopIntBothPaths)
{
    StackArray<int, 2> s;
    EXPECT_FALSE(s.try_pop().has_value());  // empty branch

    s.emplace(123);        // uses push(T&&)
    auto v = s.try_pop();  // value branch
    ASSERT_TRUE(v.has_value());
    EXPECT_EQ(*v, 123);

    EXPECT_FALSE(s.try_pop().has_value());  // empty again
}

Linked-List Stack

#pragma once

#include "ds/IStack.hpp"

#include <memory>
#include <stdexcept>
#include <utility>

namespace ds
{

template <typename T>
class StackList : public ds::IStack<T>
{
public:
    void push(const T& v) override
    {
        push_impl(v);
    }

    void push(T&& v) override
    {
        push_impl(std::move(v));
    }

    [[nodiscard]] T pop() override
    {
        if (is_empty())
        {
            throw std::runtime_error("StackList::pop: stack is empty");
        }

        auto temp = std::move(head_);  // keep strong exception safety
        head_ = std::move(temp->next);
        return std::move(temp->data);
    }

    [[nodiscard]] bool is_empty() const noexcept override
    {
        return head_ == nullptr;
    }

private:
    struct Node
    {
        template <class U>
        Node(U&& d, std::unique_ptr<Node> n) : data(std::forward<U>(d)), next(std::move(n))
        {
        }

        T data;
        std::unique_ptr<Node> next;
    };

    template <class U>
    void push_impl(U&& v)
    {
        head_ = std::make_unique<Node>(std::forward<U>(v), std::move(head_));
    }

    std::unique_ptr<Node> head_;
};

}  // namespace ds

Info

Both behave as “stacks” (LIFO),
but the data structure differs — and so do memory and speed trade-offs.

Usage Example

#include "ds/StackList.hpp"

#include <gtest/gtest.h>

using ds::StackList;

TEST(StackList, PushPopBasic)
{
    // Arrange
    StackList<int> s;
    EXPECT_TRUE(s.is_empty());

    s.push(1);
    s.push(2);

    EXPECT_FALSE(s.is_empty());
    EXPECT_EQ(s.pop(), 2);
    EXPECT_EQ(s.pop(), 1);
    EXPECT_TRUE(s.is_empty());
}

TEST(StackList, EmplaceAndTryPop)
{
    StackList<std::string> s;

    s.emplace(3, 'x');  // "xxx"
    auto v = s.try_pop();

    ASSERT_TRUE(v.has_value());
    EXPECT_EQ(*v, "xxx");
    EXPECT_FALSE(s.try_pop().has_value());
}

TEST(StackList, UnderflowThrows)
{
    StackList<int> s;
    EXPECT_THROW((void) s.pop(), std::runtime_error);
}

TEST(StackList, PushByReference)
{
    StackList<std::string> s;
    std::string str = "hello";

    s.push(str);
    str = "world";
    s.push(std::move(str));

    EXPECT_EQ(s.pop(), "world");
    EXPECT_EQ(s.pop(), "hello");
}

7. Why ADTs Matter

Info

Abstract Data Types are the bridge between algorithms and data structures.

They let us:

• Design algorithms independently of the underlying data representation.
• Write clean interfaces that can evolve without breaking the rest of the code.
• Reason about correctness and complexity mathematically.

Info

In other words, they separate conceptual behavior from implementation detail.

Using an ADT via its Interface

8. Common ADTs You’ll Encounter

Here’s a list of the most fundamental ADTs that nearly every program uses:

ADT	Description	Common Implementations
Stack	LIFO (Last In, First Out) collection	Array, Linked List
Queue	FIFO (First In, First Out) collection	Circular Buffer, Linked List
Deque	Double-ended queue	Dynamic Array, Doubly Linked List
List / Sequence	Ordered collection	Array, Linked List
Set	Unique elements, no duplicates	Hash Table, Balanced Tree
Map / Dictionary	Key–value pairs	Hash Map, Balanced Tree
Priority Queue	Elements with priority order	Heap
Graph	Nodes + edges connecting them	Adjacency List, Matrix

Info

Each of these defines behavior abstractly — you can implement them differently for different trade-offs.

9. Abstraction, Encapsulation, and Reuse

ADTs promote:

• Abstraction — hiding the details of how operations are performed.
• Encapsulation — protecting internal state.
• Reusability — algorithms can work with any structure that satisfies the same interface.

That’s why most programming libraries — from the C++ STL to Python collections — are built around ADTs at their core.

10. Key Takeaways

Tips

• An Abstract Data Type (ADT) defines what operations can be done and how they should behave, but not how they are implemented.
• A Data Structure is a specific way of implementing that ADT.
• ADTs make it possible to separate design from implementation.
• Understanding ADTs helps you reason about algorithms, performance, and correctness at a deeper level.