Section 7 - Data structures Flashcards
what is a queue
- FIFO
- new elements added to the end
- elements only retrieved from the start
what are the queue operations
- enqueue: add an item
- dequeue: remove an item
- isempty: checks if queue is empty
- isfull: checks if queue is full
what is a linear queue
as items leave the queue, all the other items move up one space (requires significant processing time)
or
pointers to the front and rear and an integer holding the size of the array and the current size of the queue
what is a circular queue
when the array fills up, the rear pointer moves to the first element
what is a dynamic data structure
collection of data in memory that can grow or shrink
the heap is a portion of memory from which space is allocated or unallocated
what is a static data structure
fixed in size, and cannot increase in size or free up space while the program is running
advantage of dynamic data strcutres compared to static
- no wasted memory
- can grow as more data is added to the data strucure
- resources only allocated as theyre needed
advantages of static structures compared to dynamic
- no pointers or data about the structure need to be stored
what is a stack
- LIFO
- items are added and removed from the top
what are stack operations
- push: add to stack
- pop: removes top item
- peek: returns top item
- isempty
- isfull
what is stack overflow and underflow
- overflow is an error when an item is pushed onto a full stack
- underflow is an error when an item us pushed from an empty stack
what is hashing
a hashing algorithm is applied to the value in the key field to transform it into an address
what is a collision
when two record keys hash to the same address
what is a binary tree
a tree where each parent node has a maximum of two child nodes
what is pre-order traversal
read the node as you pass the left of it
