fundamentals of data structure Flashcards
what is a static data structure
- a data structure fixed in size which cannot increase in size or free up memory while the programming is running.
e. g. an array
what is a dynamic data structure
- a collection of data in memory which can increase or decrease in size using heap
- heap allocates and de-allocates space as its needed
e. g. linked list
what is a queue
- a first in first out (FIFO) data structure.
- elements are added to the end of the queue and removed form the front.
- this sequence is determined by the order they are placed in the queue
what is a linear queue
- a queue implemented with pointers to the front and rear of the queue.
- rear points to the last item in queue and front points to the first
- an integer holding the arrays max size is created
- a variable holding the number of current items is created
- items cannot be added to the front even if those elements are free
- they are added to the back until the rear pointer points to the last element in queue
what is a circular queue
-a queue where the rear pointer points to the fist element when another item is added if the first element is free and the array is full
what is a priority queue
- a queue where items are removed from the front but their place in queue is determined by priority.
- this makes it possible for items to join the front of the queue.
- this can be implemented by checking each new items priority against the the current
what is a stack
- a last in, first out(LIFO) data structure
- items are added to the top and removed form the top
name 4 uses for stacks
- calculations
- subroutines: hold and return memory addresses when subroutines are called
- browsers: hold webpages allowing you to move back and forth between them
- undo: last operation is popped from the stack and undone
name 5 stack operations
- push(item) :adds new item to the top of the stack
- pop() :removes item form the top of the stack
- peek() : returns item on the top of the stack but does not pop it
- isEmpty() : checks if stack is empty
- isFull() : checks if stack is full
name 3 uses of a queue
- print jobs: first jobs put in are printed first.
- character typed: held in queue on keyboard buffer.
- simulation problems: customers arriving at checkouts
name 4 queue operations
- enQueue(item) :adds new item to the end of the queue
- deQueue() :removes item form the front of the queue
- isEmpty() :checks if queue is empty
- isFull() :checks if queue is full
what are stack underflow and stack overflow
- stacks have a maximum size as memory cannot grow
- if a stack is full and an attempt to push an item is made an overflow error will occur
- if a stack is empty and an attempt to pop an item is made an underflow error will occur
what is a call stack
a stack data structure is used to store information about a subroutine while the program is running
what are 3 functions of a call stack
- holding the return address: keeping track of the address of the instruction that control should return to
- holding parameters:
- local variables: each call to a subroutine gets its own space for its local variables without using heap space
what is a graph
-a data structure used to
represent more complex relationships. using a set of vertices/nodes connected by edges/arcs