COMP1927 - Abstract Data Types

And ADT is a data type, defined by the set of operations that may be performed on it, rather than its own characteristics.

In its specification we can design the function prototypes which allow us to interact with it, as well as the actual data type itself.

The reason it is ‘abstract’ is because we’re thinking higher level – what can we do with it, rather than how it is done. So the user/client/etc calls a function with the ADT passed into it, and that is all they know.

Benefits

  • they allow us to change our implementation without changing anything on the client’s end
  • they allow modulisation of a project, as it creates a standard through which people can pluc code and allow it to interact
  • hides information from client; simple and secure
  • structured for readability, and hence maintainability

Interface, Implementation and Client

  • The interface will be a prototype (header file) that specifies the ADT.
    • The interface stores the functions, what they do, what they take in and what they return.
    • Essentially the interface is the middle ground between the client and the implementation. It is the standard that allows the back-end implementation to change.
  • The client will contain the main function, and will call on the interface functions as needed.
  • The implementation will have the data structure and the functions set out in the interface.

A First Class ADT is essentially one that has a ‘new’ or ‘create’ function, to allow multiple versions of your data type.

Stacks and Queues

Stacks are Last In First Out, meaning they are like a stack of pancakes; you take them off in the reverse order they were put on.

Queues are First In First Out, meaning they work just like their name; the person at the front of the line is served first.

Stacks and Queues can both be implemented using either arrays (easiest, faster to access) or linked lists (more space efficient).

They both have a set of standard functions that go with them:
(and potentially others. The first four are the most commonly known ones)

  • create
  • delete
  • pop
  • push
  • isempty
  • queryheight
  • printstack
  • printfirstelement

Test Cases for Stacks and Queues:

  • creation
    • is stack empty?
  • stack overflow (pushing a full stack)
  • stack underflow (popping an empty stack)

essentially we need to check all our boundary cases and possibilities for error

Black Box vs White Box Testing (For ADTs):

Black Box Testing essentially means that you’re testing input->output correlation, whilst ignoring the actual processes that go on.
This makes it perfect for testing ADTS; the client writes a test function, and checks that all the interface functions perform as expected, and to their requirements.
White Box Testing is about testing the internal functions of the ADT, and hence cannot be done by the client. It is done during the development phase.