7. data structures Flashcards
data strucutre
is a format used to store, organise and manage data in a way that allows for efficient access and modification for the needs of the program
abstract data type
is a logical description of how the data is viewed and the operations that can be performed on it, but how this is done is not necessarily known by the user
ADT
queues
stacks
trees
graphs
advantages of ADT
+ can be easily shown in graphical form
+ its not had to understand how to perform operations such as adding, deleting or counting elements in each structure
data abstraction
process of simplifying complex data structures by providing a simple interface and hiding the underlying details.
example of data abstraction
its up to the programmer who creates the data structure to decide how to implement it, and it may be built in to the programming language
by providing this level of abstraction we are creating an encapsulation around data.
encapsulation
information hiding
queue
FIFO data structure. new elements may only be added to the end of a queue, and elements may only be retrieved from the front of a queue.
the sequence of data items in a queue is determined by the order in which they are inserted.
the size of the queue depends on the number of items in it.
queue application (1)
output waiting to be printed is commonly stored in a queue on disk. in a room full of networked computers, several people may send work to be printed at more or less the same time. by putting the output into a queue on disk, the output is printed on a first come, first served basis as soon as the printer is free.
queue application (2)
characters typed at a keyboard are held in a queue in a keyboard buffer
queue application (3)
stimulation program - attempts to model a real-life situation so as to learn something about it
stimulation program example
a program that stimulates customers arriving at random times at check-outs in a supermarket store, and taking random times to pass through the checkout.
with the aid of a stimulation program, the optimum number of check-out counters can be established.
enQueue(item)
add a new item to the rear of the queue
deQueue()
remove the front item from the queue and return it
isEmpty()
tests to see whether the queue is empty
isFull()
test to see whether queue is full
static data structure
organisation or collection of data in memory that is fixed in size.
e.g. array
- maximum size needs to be known in advance
- memory can’t be reallocated once program is running
dynamic data structure
organisation or collection of data in memory that has ability to grow or shrink in size. it does this with the aid of the heap.
e.g. linked lists or queues
- allows the programmer to control exactly how much memory will be used
- unused memory is allocated or de-allocated as needed
- maximum size of data structure is not known in advance
- can be given arbitrary maximum to avoid causing memory overflow
dynamic data structure advantage
+ makes efficient use of memory because the data structure only uses as much memory as it needs
dynamic data structure disadvantage
- dds run the risk of ‘overflow’ error, this happens when it exceeds its allowed limit. can also cause an ‘underflow’ error if it becomes empty
- harder to program because the code needs to keep track of the data structures size and location of items inside it at all times
static data structure advantage
+ memory allocation is fixed which means there will be no issues with adding and removing items from the data structure
+ easier to program as there isn’t a requirement to check on the size of the data structure at any point before accessing it
static data structure
- can be very inefficient as memory for the data structure is set aside at the start of the program but might not be utilised
implementing a linear queue
- as items leave the queue, all of the other items move up one space so that the front of the queue is always the first element of the structure
- can be implemented with pointers to the front and rear of the queue. an integer holding the size of the array (the maximum size of the queue
however, clearly a problem will arise as many items are added to and deleted from the queue, as space is created at the front of the queue which cannot be filled, and items are added until the rear pointer points to the last element of the data structure
