praxis.ibLog in
B4.1.1Properties and purpose of ADTs in programming
0/6
B4.1 Fundamentals of ADTsB4.1.1

Properties and purpose of ADTs in programming

Explain the properties and purpose of ADTs in programming

AHL≈ 50 minCommand term: ExplainFree lesson

In this lesson

  • Describing an ADT as a set of values and the operations on them, independent of how it is implemented
  • Distinguishing an ADT’s interface (what it does) from its implementation (how it does it)
  • Explaining the properties of ADTs: defined operations, abstraction, encapsulation, modularity and reusability
  • Explaining why programmers use ADTs

LearnWhat, not how

    0 of 4

    LearnCommon ADTs and their operations

    ADTBehaviourAccessInsertionDeletion
    ListItems in a sequence, each at a positionget(i)add(item), insert(i, item)remove(i)
    StackLast in, first out (LIFO)peek()push(item)pop()
    QueueFirst in, first out (FIFO)peek()enqueue(item)dequeue()
    SetDistinct items, no ordercontains(item)add(item)remove(item)
    Map (dictionary)Each key is linked to one valueget(key)put(key, value)remove(key)

    Most ADTs also have operations such as isEmpty() and size(). The names vary between languages and libraries; the behaviour is what defines the ADT.

    LabSame queue, different insides

    The program on the left only calls the queue’s operations. On the right you can look inside two different implementations of the same Queue ADT.

    The program (uses only the operations)

    Use the buttons above.

    Output:

    Inside the Queue (hidden from the program)

    1. [0]·
    2. [1]·
    3. [2]·
    4. [3]·

    front = 0, count = 0, capacity = 4

    • Not done: Enqueue at least two items and dequeue one
    • Not done: After a few operations, switch the implementation and compare the program and its output
    • Not done: Fill the array implementation so that it has to grow, and look inside it

    CodeOne interface, two implementations

    from abc import ABC, abstractmethod
    class Queue(ABC):
    @abstractmethod
    def enqueue(self, item): pass
    @abstractmethod
    def dequeue(self): pass # returns None if the queue is empty
    @abstractmethod
    def peek(self): pass
    @abstractmethod
    def isEmpty(self): pass
    class ArrayQueue(Queue):
    def __init__(self):
    self.__items = [None] * 4
    self.__front = 0
    self.__count = 0
    def enqueue(self, item):
    size = len(self.__items)
    if self.__count == size: # full: copy into a bigger array
    bigger = [None] * (size * 2)
    for i in range(self.__count):
    bigger[i] = self.__items[(self.__front + i) % size]
    self.__items = bigger
    self.__front = 0
    self.__items[(self.__front + self.__count) % len(self.__items)] = item
    self.__count = self.__count + 1
    def dequeue(self):
    if self.__count == 0:
    return None
    item = self.__items[self.__front]
    self.__items[self.__front] = None
    self.__front = (self.__front + 1) % len(self.__items)
    self.__count = self.__count - 1
    return item
    def peek(self):
    return None if self.__count == 0 else self.__items[self.__front]
    def isEmpty(self):
    return self.__count == 0
    class Node:
    def __init__(self, data):
    self.data = data
    self.next = None
    class LinkedQueue(Queue):
    def __init__(self):
    self.__head = None
    self.__tail = None
    def enqueue(self, item):
    n = Node(item)
    if self.__tail is None:
    self.__head = n
    else:
    self.__tail.next = n
    self.__tail = n
    def dequeue(self):
    if self.__head is None:
    return None
    item = self.__head.data
    self.__head = self.__head.next
    if self.__head is None:
    self.__tail = None
    return item
    def peek(self):
    return None if self.__head is None else self.__head.data
    def isEmpty(self):
    return self.__head is None
    # This function only uses the Queue's operations: it works with any implementation.
    def serve(q):
    for name in ["Ana", "Ben", "Cy", "Dee", "Eli"]:
    q.enqueue(name)
    print(q.dequeue(), q.dequeue(), "| next:", q.peek(), end="")
    while not q.isEmpty():
    q.dequeue()
    print(" | empty:", q.isEmpty())
    serve(ArrayQueue())
    serve(LinkedQueue())
    Output
    Ana Ben | next: Cy | empty: True
Ana Ben | next: Cy | empty: True

    Queue lists the operations. ArrayQueue and LinkedQueue carry them out in completely different ways, but serve is written only in terms of the operations, so it gives the same output with either. Their attributes are private, so no other code can disturb the order of the queue.

    CheckInterface or implementation?

    Does each statement describe the Queue ADT (what any queue does) or one particular implementation (how it does it)?

    1. dequeue() removes and returns the item that has waited longest
    2. The items are kept in an array with a front index that wraps round
    3. peek() returns the front item without removing it
    4. When the array is full, its contents are copied into one twice the size
    5. Each item is stored in a node that refers to the node behind it
    6. isEmpty() returns true when there are no items

    CheckQuick check

    A program needs a print queue in which jobs must never be able to jump ahead of others. How does using a Queue ADT help to guarantee this?

    ExamWorked exam answer

    A team is adding an undo feature to a text editor and decides to use a Stack ADT. Explain how using the ADT helps the team to develop the feature.

    [3]
      Try writing your own answer first.

      ReviewMistakes examiners see

      Misconception

      Treating an ADT and a data structure as the same thing: a queue (ADT) can be implemented with an array or a linked list (data structures).

      Misconception

      Defining an ADT only as “a data type made by the programmer”, without mentioning its operations.

      Misconception

      Listing properties such as “encapsulation” without saying what they mean for the scenario in the question.

      Exam tip

      In explanations, link the property to its effect: e.g. encapsulation → data can only change through the operations → it cannot be put into an invalid state.

      Exam practiceExam-style questions

      3 questions · 7 marks. Answer each one first, then mark it yourself against the markscheme. Your answers are saved in this browser only.

      Scenario

      A school’s printing system receives print jobs from many computers and sends them to a single printer. The jobs are held in a Queue ADT. At present the queue is implemented with a fixed-size array of 50 jobs, which fills up on busy days.

      (a)Outline · AO2[2]

      Outline why a queue, rather than a stack, is the appropriate ADT for the print jobs.

      (b)Explain · AO3[3]

      The developers replace the fixed-size array with an implementation that can grow. Explain why the rest of the printing system does not need to be changed.

      (c)Explain · AO3[2]

      A teacher asks for a feature that would let any computer move its own job to the front of the queue. Explain how the use of the Queue ADT prevents this from being added without the developers’ agreement.

      0 / 7

      0 of 3 questions marked. Mark every question to see your total.

      Exam-style questions written for Praxis IB in the format of the 2027 specimen papers. They are not IB past-paper questions.