Data structures Flashcards
def Variable
a Variable is a named reference to a memory location that stores data that can change during the runtime of the program
why is declaring variable type important
So that the computer knows how much memory space it has to allocate for the data
def Constant
named reference to a memory location where the data inside the constant cannot change during the runtime of the program
whats an ADT(abstract data type)
ADT is logical description of how we view data and the possible operations
e.g queue of print jobs, stack of books, list of tasks to do
Only concerned w/ what data is representing, not how its constructed
2d array: array[x,y]
which is column which is row
row = x
column = y
Remember matrices (3x1)
What are the pointers used in a queue
and the important variables to use in queue
Front
Rear
maxSize
currentSize
In memory, after the first elements memory location, where are the other elements stored
in the next consecutive memory location
In low level langs, amount of data needed 4 array is reserved, starting from 1st reserved mem location, it checks the next mem location, until end of reserved mem locations 4 array.
where do dynamic data structures allocate and deallocate memory from
the heap - an area of memory used for ____________________
3 types of queues
linear
circular
priority
in what manner do queues operate?
FIFO
advantages priority queue
gives preference to more important items
how do priority queues work
Items qiven priority
If item has higher priority than item in front of it, it can jump in front of it
If same or greater, stay put
in what manner do stacks operate
FILO
4 operations of a queue
enQueue - add an item to the REAR of the queue
deQueue - remove and return an item from the FRONT of the queue
isFull - check if queue is full
isEmpty - check if queue is empty
Circular queues
Reuse the empty spaces freed by dequeueing from front of the array
(rear + 1) MOD max
excessive amount of allocation without deallocation leads to
overflow
example dynamic data structre
example static data structure
dynamic: list
static: array
advantage using queues in a list
list is dynamic data structure, will use enough memory for number of elements inside the list
disadvantage using queues as a list
can keep adding items to the list - eventually all the memory will be exhausted and cant keep adding more
To solve this, make it so list has maxsize
Can change the maxsize when needed if need to add more items
advantages of linear queues (created using arrays)
simple to program
predictable memory usage
what to do w/ pointers when dequeue item
move the front pointer (and rear if needed)
You dont actually delete item
When need to add to slot where item is but not in queue, you overwrite it
Saves processing time
advantages circular queue
can reuse free spaces
