Abstract data types: an operation contract
Introduced| English | Meaning |
|---|---|
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | A specification of stored values and permitted operations that does not depend on a particular implementation. |
| stack/stæk/ | A last-in, first-out data structure in which items are added and removed at the same end. |
| queue/kjuː/ | A data structure in which items are normally removed in the order they were added. |
Programming with abstract data types, 1974
- In 1974 Barbara Liskov and Stephen Zilles published "Programming with Abstract Data Types". They argued that a data type should be defined by what its operations do, not by how it is stored. Liskov later received the 2008 Turing Award, partly for this work.
- An abstract data type 抽象数据类型 (ADT) is a contract: a set of operations and the rules they obey. A stack 栈 and a queue 队列 are the classic examples.
According to Liskov and Zilles, how should a data type be defined?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The contract, not the storage.
The operation contract
- The contract says what each operation does and when it is allowed:
popon an empty stack is an error. - The implementation (array or linked list) is hidden behind the contract.
The contract can say that pop on an empty stack is an error.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
It states when operations are allowed.
Stack: last in, first out
push(x)adds to the top;pop()removes the top;peek()reads it. LIFO.- Uses: undo history, the call stack, checking brackets.
Push 4, push 7, push 2, pop. What is on top now?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
2 was popped; LIFO.
Queue: first in, first out
enqueue(x)adds at the rear;dequeue()removes from the front. FIFO.- Uses: print jobs, buffering, breadth-first search.
Same arrivals, different removal order
Trace A, B, C, two removals, then D. A queue keeps C then D; the same operations on a stack keep A then D. Empty removal is explicitly guarded.
A queue starts empty, receives 9 items and dequeues 6. How many items remain?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
9 − 6 = 3.
Match each use to the ADT.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
LIFO against FIFO.
Worked example: checking brackets with a stack
Check ( [ ] { } ).
read action stack
( push (
[ push ( [
] pop [ — matches (
{ push ( {
} pop { — matches (
) pop ( — matches empty
- End: the stack is empty and every pop matched, so the brackets are balanced.
- For
( ], popping(against]fails — unbalanced. LIFO is exactly what nesting needs.
"( ]" is balanced.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Popping ( against ] fails.
Linked lists and trees
- A linked list stores nodes with pointers; insertion is cheap, indexing is slow.
- A binary search tree keeps left < node < right, giving O(log n) search when balanced.
An ADT is not its implementation. "A stack is an array" confuses the two. A stack is defined by push, pop and LIFO; an array is one way to build it.
A stack is the same thing as an array.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
An array is one implementation.
An ADT is a contract of operations and rules, independent of storage. Stacks are LIFO (push, pop), queues are FIFO (enqueue, dequeue); choose the ADT whose rules fit the problem, and keep the implementation hidden.
Trace a queue through enqueue A, enqueue B, dequeue, enqueue C, enqueue D, dequeue. Give the final contents front to rear.
Front out, rear in.