In Your Textbook: Abstract Data Types

Textbooks separate what a structure does (an abstract data type, such as a stack) from how it's built (a data structure, such as an array or a linked list). In code, that line is an interface, and any class that keeps its promise can stand behind it.

Journeyman · Data Structures · Updated

By

After this lesson you can

  • Tell an abstract data type (what it does) from a data structure (how it's built)
  • Read an interface that describes a stack, and name two classes that could implement it

Key takeaways

  • An abstract data type (ADT) is what a structure does: its operations and their rules, such as a stack's push, pop and peek, last in, first out.
  • A data structure is how it's built: a growing array, a linked list, a ring buffer.
  • One ADT can be built several ways, with different costs; code written against the ADT works with any of them.
  • In C#, Java and TypeScript an ADT is written as an interface; Python uses an abstract base class; JavaScript relies on the methods being there.

In this chapter, "a stack" meant two different things. Sometimes it meant a rule: push, pop, peek, the last in is the first out. Sometimes it meant a build: a growing array with the top at the end. Textbooks, exams and interviewers keep those apart, with two names, and so does well-organized code. This optional lesson gives you the textbook words, and shows how each language writes the line between them.

What it does, and how it's built

Think of a vending machine. The front panel is a promise: put money in, press B4, and a snack drops out. That's all you need to know to use it. Inside, one machine uses spiral coils, another a robot arm, another a conveyor belt. Each builder chooses, and each choice has its own costs, but the front panel is the same.

  • An abstract data type, or ADT, is the front panel: the operations and the rules they follow. A stack is an ADT: push, pop, peek, last in, first out. A queue is an ADT: enqueue, dequeue, peek, first in, first out. Nothing about arrays or nodes.
  • A data structure is what's inside: how the items are actually kept. A growing array, a linked list and a ring buffer are data structures.

So "a stack built on a growing array" and "a stack built on a linked list" are one ADT, two data structures. Both keep the stack's promise; they differ in costs (a moving day now and then, or an extra reference per item) and in memory.

One box at the top labeled "Stack (what it does): push, pop, peek; last in, first out". Two arrows lead down from it to two boxes labeled "how it's built": on the left, a growing array whose last slot is marked "top"; on the right, a linked list whose head is marked "top". A note under both says "same promise, different costs"

Writing the promise down: an interface

In code, the front panel is an interface: a list of methods, with no code inside them, that a class promises to have. Code that uses the stack asks only for "something that keeps the stack's promise", and any class that does can be handed in.

This program writes the stack's promise once, builds it two ways, and uses both with the same Reverse function: the last song pushed is the first one popped, so a playlist comes back reversed.

List<string> songs = new List<string> { "Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats" };
Console.WriteLine("Array stack: " + string.Join(", ", Reverse(new ArrayStack(), songs)));
Console.WriteLine("Linked stack: " + string.Join(", ", Reverse(new LinkedStack(), songs)));

List<string> Reverse(ISongStack stack, List<string> items)
{
    foreach (string item in items) stack.Push(item);
    List<string> reversed = new List<string>();
    while (!stack.IsEmpty) reversed.Add(stack.Pop());
    return reversed;
}

interface ISongStack
{
    void Push(string song);
    string Pop();
    bool IsEmpty { get; }
}

class ArrayStack : ISongStack
{
    private List<string> items = new List<string>();
    public void Push(string song) => items.Add(song);
    public string Pop()
    {
        string top = items[items.Count - 1];
        items.RemoveAt(items.Count - 1);
        return top;
    }
    public bool IsEmpty => items.Count == 0;
}

class LinkedStack : ISongStack
{
    private record Node(string Song, Node? Next);
    private Node? top;
    public void Push(string song) => top = new Node(song, top);
    public string Pop()
    {
        string song = top!.Song;
        top = top.Next;
        return song;
    }
    public bool IsEmpty => top == null;
}
Array stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus
Linked stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus
interface SongStack {
    void push(String song);
    String pop();
    boolean isEmpty();
}

class ArrayStack implements SongStack {
    private List<String> items = new ArrayList<>();
    public void push(String song) { items.add(song); }
    public String pop() { return items.remove(items.size() - 1); }
    public boolean isEmpty() { return items.isEmpty(); }
}

class LinkedStack implements SongStack {
    private record Node(String song, Node next) {}
    private Node top;
    public void push(String song) { top = new Node(song, top); }
    public String pop() {
        String song = top.song();
        top = top.next();
        return song;
    }
    public boolean isEmpty() { return top == null; }
}

List<String> reverse(SongStack stack, List<String> items) {
    for (String item : items) stack.push(item);
    List<String> reversed = new ArrayList<>();
    while (!stack.isEmpty()) reversed.add(stack.pop());
    return reversed;
}

void main() {
    List<String> songs = List.of("Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats");
    IO.println("Array stack: " + String.join(", ", reverse(new ArrayStack(), songs)));
    IO.println("Linked stack: " + String.join(", ", reverse(new LinkedStack(), songs)));
}
Array stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus
Linked stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus
from abc import ABC, abstractmethod


class SongStack(ABC):
    @abstractmethod
    def push(self, song): ...

    @abstractmethod
    def pop(self): ...

    @abstractmethod
    def is_empty(self): ...


class ArrayStack(SongStack):
    def __init__(self):
        self.items = []

    def push(self, song):
        self.items.append(song)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0


class LinkedStack(SongStack):
    def __init__(self):
        self.top = None

    def push(self, song):
        self.top = (song, self.top)

    def pop(self):
        song, self.top = self.top
        return song

    def is_empty(self):
        return self.top is None


def reverse(stack, items):
    for item in items:
        stack.push(item)
    reversed_items = []
    while not stack.is_empty():
        reversed_items.append(stack.pop())
    return reversed_items


songs = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats"]
print("Array stack: " + ", ".join(reverse(ArrayStack(), songs)))
print("Linked stack: " + ", ".join(reverse(LinkedStack(), songs)))
Array stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus
Linked stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus
// Any object with push, pop and isEmpty keeps the stack's promise.
class ArrayStack {
  items = [];
  push(song) { this.items.push(song); }
  pop() { return this.items.pop(); }
  isEmpty() { return this.items.length === 0; }
}

class LinkedStack {
  top = null;
  push(song) { this.top = { song, next: this.top }; }
  pop() {
    const song = this.top.song;
    this.top = this.top.next;
    return song;
  }
  isEmpty() { return this.top === null; }
}

function reverse(stack, items) {
  for (const item of items) stack.push(item);
  const reversed = [];
  while (!stack.isEmpty()) reversed.push(stack.pop());
  return reversed;
}

const songs = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats"];
console.log(`Array stack: ${reverse(new ArrayStack(), songs).join(", ")}`);
console.log(`Linked stack: ${reverse(new LinkedStack(), songs).join(", ")}`);
Array stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus
Linked stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus
interface SongStack {
  push(song: string): void;
  pop(): string;
  isEmpty(): boolean;
}

class ArrayStack implements SongStack {
  private items: string[] = [];
  push(song: string): void { this.items.push(song); }
  pop(): string { return this.items.pop() as string; }
  isEmpty(): boolean { return this.items.length === 0; }
}

type StackNode = { song: string; next: StackNode | null };

class LinkedStack implements SongStack {
  private top: StackNode | null = null;
  push(song: string): void { this.top = { song, next: this.top }; }
  pop(): string {
    const node = this.top as StackNode;
    this.top = node.next;
    return node.song;
  }
  isEmpty(): boolean { return this.top === null; }
}

function reverse(stack: SongStack, items: string[]): string[] {
  for (const item of items) stack.push(item);
  const reversed: string[] = [];
  while (!stack.isEmpty()) reversed.push(stack.pop());
  return reversed;
}

const songs = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats"];
console.log(`Array stack: ${reverse(new ArrayStack(), songs).join(", ")}`);
console.log(`Linked stack: ${reverse(new LinkedStack(), songs).join(", ")}`);
Array stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus
Linked stack: Paper Boats, Slow Rain, Lemon Skies, Midnight Bus

Reverse never asks which kind of stack it got: it only uses the promise. Each language draws the line its own way:

  • C# and Java: an interface lists the methods, and each class says it keeps the promise (: ISongStack, implements SongStack). C# names interfaces with a leading I by habit. Both build the linked stack's nodes with a small record, a class that only holds values. To keep the example short, neither stack checks for an empty pop here; the EditStack in Undo the Last Thing First: Stacks shows that check.
  • Python: an abstract base class (ABC) with @abstractmethods; a class that inherits from it and leaves a method out can't be created. The linked stack's nodes here are pairs, (song, next).
  • JavaScript: no interfaces. Any object with the right methods works, which programmers call duck typing ("if it quacks like a duck…"). The comment at the top is the promise.
  • TypeScript: an interface, checked when the code compiles and gone when it runs.

What your class or interview expects

  • "Is a stack a data structure?" Strictly, a stack is an ADT, and an array-based stack or a linked stack is a data structure that implements it. Everyday developers say "data structure" for both, and that's fine outside an exam.
  • "Implement a queue." The interviewer usually wants the ADT's operations and their Big-O, then a build that keeps every one at O(1): a linked list with a head and a tail, or a ring buffer.
  • The list ADT (get, insert, remove by position) is built by both growing arrays and linked lists, which is why their cost cards could be compared operation by operation in Arrays vs Linked Lists.
  • In your language's library, the ADT and the structure often share a name: Java's Deque is an interface (the ADT), and ArrayDeque and LinkedList are two classes that implement it.

Try it. Write a third class that keeps the stack's promise, say a CountingStack that also counts how many pushes it has had, and pass it to Reverse. Did you need to change Reverse?

Check yourself

2 questions to try on the lesson page.

So what

Separating "what it does" from "how it's built" lets you swap one build for a faster one without touching the code that uses it. It's also the vocabulary your textbook, your exam and your interviewer will use, and now it's yours too.

Key terms

Cheat sheets