# Abstract Data Use

Computer Science I · Programming II · https://tryals.app/learn/computer-science-i/abstract-data-use

## Abstract Data Types

A powerful idea in programming is separating **what** data does from **how** it does it. An **abstract data type (ADT)** is defined by its **operations and their behavior**, not its internal representation. A **stack** ADT uses **push**, **pop**, and **peek** in a last-in-first-out order, whether backed by an array or linked list.

The **abstraction barrier** (interface) divides public operations from hidden internals. **Information hiding** (encapsulation) lets implementations be swapped without changing user code. Program against the **interface**, not the internal machinery.

| Concept | Definition |
| --- | --- |
| **ADT** | Defined by operations, not internals |
| **Barrier** | Line between public calls and private code |

> **Pitfall:** Reaching through the abstraction barrier. Relying on internal storage breaks code when implementations change. Always use published operations.

## Classes and Encapsulation

An ADT becomes concrete via a **class**, bundling **fields** (internal data) and **methods** (operations). An **object** is an **instance** of a class. A **constructor** runs at creation to establish the **class invariant**—the property that must always hold true.

| Modifier | Access Level |
| --- | --- |
| **private** | Reachable only inside the class |
| **public** | Methods forming the class **interface** |

**Encapsulation** makes invariants defensible by marking fields **private**. 

> **Pitfall:** Making fields public or adding getters/setters for all of them. This turns a class into an unguarded bag of variables, letting callers violate the invariant.

## Practice questions

6 of this lesson's 12 practice questions, with answers. The full set is in the app.

### 1. A stack ADT implemented with a fixed-size array can overflow when pushed too many times; the same ADT over a linked list cannot. Does that mean the array implementation is wrong?

A. Yes, because the linked implementation is available and is strictly better.
B. No, because overflow is a hardware limitation rather than a property of the implementation.
C. Yes, because any implementation that can fail is incorrect by definition.
D. No - it means the ADT's specification did not say.

**Answer:** D. No - it means the ADT's specification did not say.

**Why:** Correctness is relative to a specification, so the question cannot be answered until one is stated. Which is why capacity limits and error behaviour belong in the interface, 'push raises StackFull at capacity' is a promise callers can program against. The linked version pays for its unboundedness in pointers and cache behaviour, and a growable array is the usual compromise.

Page: https://tryals.app/practice/computer-science-i/abstract-data-use/a-stack-adt-implemented-with-a-fixed-size-array-can-overflow-when

### 2. A team replaces a stack's array implementation with a linked-node one. The published operations behave identically. Select every piece of calling code that keeps working.

A. Code calling pop in an empty-stack error handler
B. Code relying on a push refused at 64 items
C. Code that pushes items and pops them in reverse order
D. Code that calls peek in a loop until size reports zero
E. Code indexing the stack's storage for the third element

**Answer:** A. Code calling pop in an empty-stack error handler; C. Code that pushes items and pops them in reverse order; D. Code that calls peek in a loop until size reports zero

**Why:** Anything built from push, pop, peek and size survives, including the documented empty-stack error. Indexing internal storage and depending on a 64-item ceiling both rest on the array's internals, which the linked version does not have, and being able to make this swap safely is the entire payoff of the abstraction barrier.

Page: https://tryals.app/practice/computer-science-i/abstract-data-use/a-team-replaces-a-stacks-array-implementation-with-a-linked-node

### 3. A library documents a function's behaviour but not its complexity. Callers then write loops assuming it is cheap. Whose mistake is it?

A. The library's alone, since complexity is always part of an interface
B. Neither, complexity is an implementation detail that should never be documented
C. The caller's alone, since undocumented behaviour must never be relied on
D. Shared, the caller assumed a guarantee the library never documented

**Answer:** D. Shared, the caller assumed a guarantee the library never documented

**Why:** Behaviour alone does not let a caller design; they plan around cost, so the omission guarantees the assumption. Real libraries promote complexity into the contract for that reason, and pay for it by constraining future implementations, which is a deliberate trade rather than an oversight.

Page: https://tryals.app/practice/computer-science-i/abstract-data-use/a-library-documents-a-functions-behaviour-but-not-its-complexity

### 4. Order what happens when an object is created and then used.

**Answer:**

1. Memory is set aside to hold the new object's fields
2. The constructor runs, with the arguments given at the point of creation
3. The constructor rejects or corrects any argument that would break the invariant
4. The object is handed back to the caller with its class invariant holding
5. A public method is called, and may assume the invariant holds on entry

**Why:** Allocation comes first because the constructor needs fields to write into. The constructor then validates before the object escapes: that ordering is the whole point, since an object handed back in a broken state can never be repaired by the methods, which were written assuming the invariant already holds. Letting the object reach the caller before validation is the error, by then any method may already have been called on it.

Page: https://tryals.app/practice/computer-science-i/abstract-data-use/order-what-happens-when-an-object-is-created-and-then-used

### 5. Because an ADT's interface says nothing about cost, two correct implementations of the same interface can differ enormously in performance.

**Answer:** True

**Why:** True. `contains` is O(n) on a list and O(1) on a hash table, and both satisfy the same interface. That is the point and the danger of an ADT: it lets you swap implementations freely, and it lets you swap in one whose costs make every caller quadratic without changing a line of them.

Page: https://tryals.app/practice/computer-science-i/abstract-data-use/because-an-adts-interface-says-nothing-about-cost-two-correct

### 6. A stack ADT is being documented. Sort each statement by whether it belongs in the published interface or is an implementation detail.

**Answer:**

- Belongs to the interface: pop removes and returns the most recently pushed element, peek returns the top element without removing it
- Is an implementation detail: The elements are held in a contiguous array of capacity 64, An integer field records how many elements are currently stored

**Why:** The interface is what callers may rely on, the behaviour of push, pop and peek, including what happens in the error case. Arrays, capacities, counters and doubling are all machinery that a linked-node implementation would replace entirely, so no caller may depend on them.

Page: https://tryals.app/practice/computer-science-i/abstract-data-use/a-stack-adt-is-being-documented-sort-each-statement-by-whether-it