fundamentals of 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

• 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

• 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

• 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

-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

• 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

• a last in, first out(LIFO) data structure - items are added to the top and removed form the top

• 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

• 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

• print jobs: first jobs put in are printed first. • character typed: held in queue on keyboard buffer. • simulation problems: customers arriving at checkouts

• 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

• 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

a stack data structure is used to store information about a subroutine while the program is running

• 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

-a data structure used to represent more complex relationships. using a set of vertices/nodes connected by edges/arcs

• undirected: the edges are bi-directional - directed: the edges are one-way

-a graph where the edges show the cost of moving from one vertex to another

• a way to implement a graph using a two dimensional array to store the information • each row and column represent a node • if the graph is weighted the value will be stored if not 1s will be used.

• a more space efficient way to implement a graph using a list. • a list of all the nodes which point to the nodes they are directly linked with. the weight can be held next to each linked node

• computer networks - weight=bandwidth • roads between towns - weights=distance • tasks in projects • states in finite state machine • web links and pages

a connected undirected graph with no cycles

• node: contains tree data edge: connects 2 nodes • root: only node with no incoming edges or parent • child: set of nodes with the same parent/ incoming edges form the same node • parent: connects with outgoing edges • subtree: set of nodes made of a parent and descendent • leaf node: a node with no children

a tree with only one root node ( a node with no parents)

• manipulating hierarchical data • making information easier to search • manipulating sorted lists of data