IB Computer Science · B4 · Abstract data types
B4.1 Abstract data types
Describe what an abstract data type is, explain why it is useful, compare it with built-in data types, and give examples such as stacks and queues.
1/6An abstract data type is defined by its behaviour
- An abstract data type is defined by its behaviour
- Hiding the implementation makes programs easier to build and change
- Abstract data types are defined by operations, not built in
- A stack removes the item that was added last
- A queue serves items in the order they arrived
- Lists, sets and dictionaries organise data in other ways
- Check your recall
- Practice: 10 questions
Part 1 of 6: An abstract data type is defined by its behaviour
Think of a vending machine. You press a button and receive a snack, but you never see the mechanism inside. You only need to know what each button does.
An abstract data type describes a kind of data by the operations allowed on it and their effects. It says nothing about how the data is stored in memory. The way the data is actually stored is a data structure, such as an array or a linked list.
One abstract data type can therefore be built in several ways. Programs that use it behave the same whichever way is chosen.
Key terms · tap one for its definition
abstract data type
An abstract data type is a description of a kind of data by its operations and their behaviour, independent of how it is stored.
data structure
A data structure is a concrete arrangement of data in memory, such as an array, that can implement an abstract data type.
Part 2 of 6: Hiding the implementation makes programs easier to build and change
Now that behaviour is separated from storage, the benefits become clear. Programmers use the type through its interface, the set of operations it offers. The code and storage that carry out those operations form the implementation.
- Code is easier to understand, because users think about operations, not memory.
- The implementation can be replaced without changing the programs that use it.
- Different programmers can work on the type and on its users separately.
- The same type can be reused in many programs.
- Errors are less likely, because data changes only through approved operations.
Key terms · tap one for its definition
interface
The interface of an abstract data type is the set of operations that users may call, together with the behaviour of each.
implementation
The implementation of an abstract data type is the code and data structure that carry out its operations.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: C · Worked explanation
Part 3 of 6: Abstract data types are defined by operations, not built in
Languages already provide simple types such as integers, Booleans and characters. A built-in data type is supplied by the language, with its storage and operations fixed in advance.
An abstract data type is different. The programmer or a library defines it, and the focus is on its operations. It is usually built from built-in types. A stack, for example, can be stored in an array.
Built-in types are ready to use, but they cannot cover every need. Programs often need data that behaves like a pile, a queue or a collection. Abstract data types fill that gap.
Built-in and abstract data types compared
- Feature
- Supplied by
- Built-in data type
- The language
- Abstract data type
- The programmer or a library
- Feature
- Described by
- Built-in data type
- Its values and basic operators
- Abstract data type
- Its operations and their behaviour
- Feature
- Storage
- Built-in data type
- Fixed by the language
- Abstract data type
- Hidden; may be implemented in several ways
- Feature
- Examples
- Built-in data type
- Integer, Boolean, character
- Abstract data type
- Stack, queue, list
Key term
built-in data type
A built-in data type is a data type supplied by a programming language, such as an integer, Boolean or character.
Part 4 of 6: A stack removes the item that was added last
A pile of plates shows how the first abstract data type behaves. You add a plate to the top, and you take a plate from the top.
A stack follows last in, first out order, often written LIFO. The operation push adds an item to the top. The operation pop removes the top item and returns it. A third operation, peek, reads the top item without removing it.
Stacks suit tasks that must undo the most recent step. Examples are an undo feature in an editor and the way a program tracks function calls. Popping an empty stack is an error, called underflow.
Worked example
Tracing stack operations
- push 4 gives a stack holding 4.
- push 7 puts 7 on top, so the stack holds 4 and 7.
- pop removes and returns 7, leaving 4.
- push 9 puts 9 on top, so the stack holds 4 and 9.
- pop removes and returns 9, leaving 4.
Answer: The pops return 7 then 9, and the stack finally holds only 4.
Key terms · tap one for its definition
stack
A stack is an abstract data type in which items are added and removed at one end, giving last in, first out order.
push
Push is the stack operation that adds an item to the top of the stack.
pop
Pop is the stack operation that removes the top item of the stack and returns it.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: A · Worked explanation
Part 5 of 6: A queue serves items in the order they arrived
A queue at a shop counter works the opposite way to a pile of plates. The person who joined first is served first.
A queue follows first in, first out order, often written FIFO. The operation enqueue adds an item at the back. The operation dequeue removes the item at the front and returns it.
Queues suit tasks that must be handled fairly, in arrival order. A common example is a set of print jobs waiting for one printer.
Key terms · tap one for its definition
queue
A queue is an abstract data type in which items join at the back and leave from the front, giving first in, first out order.
enqueue
Enqueue is the queue operation that adds an item to the back of the queue.
dequeue
Dequeue is the queue operation that removes the item at the front of the queue and returns it.
Part 6 of 6: Lists, sets and dictionaries organise data in other ways
Stacks and queues limit where items enter and leave. Other abstract data types give more freedom, and each has its own operations.
- A list keeps items in order and allows access, insertion and removal at any position.
- A set holds distinct items, so duplicates are not stored.
- A dictionary stores key and value pairs and finds a value from its key.
Each of these can be implemented in several ways, for example using an array. The user only needs to know the operations.
Key terms · tap one for its definition
list
A list is an abstract data type that holds an ordered collection of items and allows access, insertion and removal at any position.
set
A set is an abstract data type that holds a collection of distinct items, with no duplicates and no required order.
dictionary
A dictionary is an abstract data type that stores key and value pairs and returns the value linked to a given key.
Check your recall[15 marks]
5 written questions. Answer each one in your head or on paper, then open the mark scheme.
- 1.Define[2 marks]
Define the term abstract data type.
Show mark schemeHide mark scheme
Model answer
An abstract data type is a description of a kind of data by the operations allowed on it and their behaviour. It does not specify how the data is stored.
- 1 mark for stating that it is described by its operations and their behaviour
- 1 mark for stating that it does not fix how the data is stored
- 2.Outline[4 marks]
Outline two reasons why abstract data types are useful in programming.
Show mark schemeHide mark scheme
Model answer
The implementation can be changed without altering the programs that use the type, because users rely only on the interface. Programs are easier to understand, because programmers think about operations rather than memory.
- 1 mark for stating that the implementation can be changed without altering code that uses it
- 1 mark for linking this to users relying only on the interface
- 1 mark for stating that code is easier to understand or reuse
- 1 mark for giving a reason, such as thinking about operations instead of storage
- 3.Distinguish[3 marks]
Distinguish between a built-in data type and an abstract data type.
Show mark schemeHide mark scheme
Model answer
A built-in data type is supplied by the language, with its storage fixed. An abstract data type is defined by the programmer or a library through its operations. Its storage is hidden and can be implemented in several ways.
- 1 mark for stating that a built-in type is supplied by the language with fixed storage
- 1 mark for stating that an abstract type is defined by the programmer or a library through its operations
- 1 mark for stating that an abstract type can be implemented in several ways
- 4.Determine[3 marks]
A stack starts empty. The operations push 5, push 8, pop, push 3, pop are carried out. Determine the values returned by the pop operations and the final contents of the stack.
Show mark schemeHide mark scheme
Model answer
The first pop returns 8 and the second pop returns 3. The stack finally holds only 5.
- 1 mark for stating that the first pop returns 8
- 1 mark for stating that the second pop returns 3
- 1 mark for stating that the final stack holds only 5
- 5.Compare[3 marks]
Compare a stack with a queue.
Show mark schemeHide mark scheme
Model answer
Both are abstract data types that add and remove items using defined operations. A stack removes the most recently added item, in last in, first out order. A queue removes the earliest added item, in first in, first out order.
- 1 mark for stating that both are abstract data types defined by their operations
- 1 mark for stating that a stack removes the most recently added item (LIFO)
- 1 mark for stating that a queue removes the earliest added item (FIFO)

Practice this topic
10 quick-fire multiple-choice questions, easy to hard. Tap an answer to see if you're right and the worked explanation. (The written questions with mark schemes are under “Check your recall” above.)
0 right0 of 10 answered
Includes the 2 quick checks in the note above.
EasyState[1 mark]
Show answer and explanation
Answer: C · Worked explanation
MediumDetermine[2 marks]
Show answer and explanation
Answer: D · Worked explanation
MediumDetermine[2 marks]
Show answer and explanation
Answer: D · Worked explanation
MediumExplain[2 marks]
Show answer and explanation
Answer: B · Worked explanation
MediumCompare[2 marks]
Show answer and explanation
Answer: A · Worked explanation
HardDeduce[2 marks]
Show answer and explanation
Answer: C · Worked explanation
HardDeduce[2 marks]
Show answer and explanation
Answer: A · Worked explanation
Hard[2 marks]
Show answer and explanation
Answer: D · Worked explanation