Unit 7 - ADTs Flashcards
(124 cards)
Elementry Data Types Examples
Boolean, char, integer, real
Composite Data Types
Array, String
Abstract Data Types examples
Stacks, Queues, Dictionaries
Abstract Data Types (definition)
A logical description of how we view data and possible operations
Static Data Types Definition
Fixed in size, cannot change size once program is running
Dynamic Data types defininition
Can grow/shrink in size once program is running as it uses the heap
The heap (memory)
A portion of memory which space is automatically allocated/ deallocated to as required
Dynamic Data Structure Uses
Queues, as maximum size is not known before implementation
Record Structure
Consists of a fixed number of variables called fields, each field can have a different data type
Records in C#
Must be defined using a dictionary or using a class
Tuples
Tuples are mutable data structures –> declared like a list
Array Limitations
Size must be declared when created, cannot grow in size, one data type (in some languages including C#)
Array Benefits
Can be any dimension, uses 0 based indexing, values are mutable
Mutable Definition
Values can be changed whilst the programming is running
enqueue(data)
Adds an element to the queue
dequeue()
Removes (and returns) element from the queue
peek()
returns element from queue without removing it from queue
is_empty()
Checks if queue is empty
is_full()
Check if queue is full (if it is static)
What is a Queue
It is a mutable fifo data structure, meaning that items are added at the back and removed from the front
Why circular queues exist?
When an item is dequeued, a space of memory is left however this is left at the front of the queues and data in a queue is only added at the back, this leaves memory being wasted and queues filling up fast, circular queues solve this problem
How do circular queues work?
Let the queue be defined as an array. If the end is pointer is at the end of the array, however the start pointer is not at the front, a circular queue means that the next item to be enqueued will be added to the first slot on the array. The pointer for the end also points to here, this means that whilst the array is not full, data can keep being enqueued and it will go around in circles
Application of Queues
Printer Queues, the thing that was printed first will be the first to be printed.
Simulations of actual queues eg in a supermarket
How do priority queues work?
Each data is given a priority, the ones with the higher priorities are nearer to the front of the queue which means they are more likely to get dequeued sooner. When data is added it is added as the last one with that priority making it possible for it to be added at the front or in the middle