Scribe logoScribeNotes & practice
Sign inStart free
  1. Notes
  2. ›IB Computer Science
  3. ›B4 Abstract data types
  4. ›B4.1 Abstract data types

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.

  • 6 min read
  • 6 parts
  • 10 questions
  • Draft
  • HL only
Start a Quick 5 on this topic→Jump to the 10 questions
1/6An abstract data type is defined by its behaviour
  1. 1An abstract data type is defined by its behaviour
  2. 2Hiding the implementation makes programs easier to build and change
  3. 3Abstract data types are defined by operations, not built in
  4. 4A stack removes the item that was added last
  5. 5A queue serves items in the order they arrived
  6. 6Lists, sets and dictionaries organise data in other ways
  7. Check your recall
  8. Practice: 10 questions
1

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.

Common mistake

An abstract data type is not a data structure. The type states what the operations do; the data structure decides how the data is stored.

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 1 done

2

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.

Exam tip

When asked why abstract data types are useful, give a benefit and say why it follows. For example, the implementation can change without altering the code that uses it.

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.

Part 2 done

Quick check

One question on the part you just read

Easy

State which description best matches an abstract data type.
Show answer and explanation

Answer: C · Worked explanation

An abstract data type is defined by its operations and their behaviour, not by how it is stored. A fixed storage format describes a built-in data type. A concrete arrangement in memory describes a data structure, which is only one way to implement the abstract type.
3

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

FeatureBuilt-in data typeAbstract data type
Supplied byThe languageThe programmer or a library
Described byIts values and basic operatorsIts operations and their behaviour
StorageFixed by the languageHidden; may be implemented in several ways
ExamplesInteger, Boolean, characterStack, queue, list
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 3 done

4

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.

Figure 1. Items enter and leave at the same end, the top. Only the top item can be reached.

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

A stack starts empty. The operations are push 4, push 7, pop, push 9, pop. Determine the values returned by pop and the final contents.
  1. 1
    push 4 gives a stack holding 4.
  2. 2
    push 7 puts 7 on top, so the stack holds 4 and 7.
  3. 3
    pop removes and returns 7, leaving 4.
  4. 4
    push 9 puts 9 on top, so the stack holds 4 and 9.
  5. 5
    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.

Part 4 done

Quick check

One question on the part you just read

Easy

State the order in which a stack removes items.
Show answer and explanation

Answer: A · Worked explanation

A stack follows last in, first out order, so the newest item is removed first. Removing the earliest item describes a queue, which is the common confusion. Removal by size or from any position is not how a stack works.
5

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.

Exam tip

When comparing the two types, name the removal order. A stack removes the newest item and a queue removes the oldest item.

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 5 done

6

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.

Go deeperImplementing a stack

A stack can be stored in an array with a variable that records the top position. Push stores an item and raises that position. Pop returns the item and lowers it.

An array has a fixed size, so pushing onto a full stack causes overflow. A linked list avoids this limit, with push and pop at its head. Programs using the stack cannot tell which version they have, which is the point of the abstraction.

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.

Note read

Check your recall[15 marks]

5 written questions. Answer each one in your head or on paper, then open the mark scheme.

  1. 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. 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. 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. 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. 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.

3.

Easy·State[1 mark]

State the operation that adds an item to the back of a queue.
Show answer and explanation

Answer: C · Worked explanation

Enqueue adds an item at the back of a queue. Dequeue removes the front item, which is the opposite action. Push and pop are stack operations, so they belong to the wrong type even though they also add and remove items.
4.

Medium·Determine[2 marks]

A stack starts empty. The operations push 2, push 6, push 1, pop, pop are carried out. Determine the item now on top of the stack.
Show answer and explanation

Answer: D · Worked explanation

Push 2, 6 and 1 gives 2, 6, 1 with 1 on top. The first pop returns 1 and the second returns 6, leaving only 2. The value 6 would be on top after a single pop, which is the result of stopping one step early.
5.

Medium·Determine[2 marks]

A queue starts empty. The operations enqueue A, enqueue B, enqueue C, dequeue, enqueue D, dequeue are carried out. Determine the item now at the front.
Show answer and explanation

Answer: D · Worked explanation

Enqueue A, B, C gives A, B, C with A at the front. Dequeue removes A, enqueue D adds D at the back, and the next dequeue removes B. The queue then holds C and D, so C is at the front. B is the front after only one dequeue.
6.

Medium·Explain[2 marks]

A programmer replaces the array inside a stack with a linked list. Programs using the stack still work unchanged. Explain why.
Show answer and explanation

Answer: B · Worked explanation

Users call push and pop through the interface and never touch the storage. The implementation can therefore change as long as the operations behave the same. An array and a linked list have different memory layouts, so a matching layout is not the reason.
7.

Medium·Compare[2 marks]

Which statement correctly compares a built-in data type with an abstract data type?
Show answer and explanation

Answer: A · Worked explanation

A built-in type comes from the language with fixed storage, while an abstract type is described by its operations and can be built in several ways. The statement that swaps these roles has them reversed. Defining an abstract type by its storage layout confuses it with a data structure.
8.

Hard·Deduce[2 marks]

A program must record ticket numbers already issued. It must never store a number twice and must check quickly whether a number is present. Order does not matter. Which abstract data type fits best?
Show answer and explanation

Answer: C · Worked explanation

A set holds distinct items, so duplicates are never stored, and order is not required. A list keeps order and would allow repeated numbers unless extra checks were added. A stack and a queue limit access to one end, so they do not suit checking whether a number is present.
9.

Hard·Deduce[2 marks]

A print server must print documents in the order they were submitted. Which abstract data type and operation send the next document to the printer?
Show answer and explanation

Answer: A · Worked explanation

Fair, arrival order needs first in, first out, so a queue fits, and dequeue removes and returns the front item. Enqueue only adds a new document at the back. A stack would print the newest document first, which breaks the required order.
10.

Hard[2 marks]

A student says, “a stack is an array.” Which response is most accurate?
Show answer and explanation

Answer: D · Worked explanation

A stack is an abstract data type, defined by operations such as push and pop. An array is a data structure that can implement it, though a linked list could be used instead. Saying a stack can only use an array ignores that the implementation is hidden and can change.

Keep going

Previous topicB3.2 OOP with multiple classes

All IB Computer Science topics →

Draft: written by Scribe and checked automatically, not yet by a subject reviewer.

Practice questions are original, written by Scribe and checked automatically for correctness.

Topic codes follow the official numbering. Not endorsed by IB Diploma Programme or any exam board.

On this page

0/6 read

  1. 1An abstract data type is defined by its behaviour
  2. 2Hiding the implementation makes programs easier to build and change
  3. 3Abstract data types are defined by operations, not built in
  4. 4A stack removes the item that was added last
  5. 5A queue serves items in the order they arrived
  6. 6Lists, sets and dictionaries organise data in other ways
  7. Check your recall
  8. Practice: 10 questions
All coursesScribeHow it worksPricingPrivacyTerms

Notes and questions are written by Scribe in our own words. Topic codes follow the official course numbering so you can find your place. Not produced or endorsed by the IB, College Board, AQA, OCR, Pearson Edexcel or any exam board.

© 2026 Scribe