Data structures

Data structures

1. Queues

   • First in first out (FIFO)
     • Can only add to the back and retrieve from the front
   • Examples of queues
     • Printing job queue
     • Characters typed at a keyboard are placed in a keyboard buffer
   • Operations on the queue
     • enQueue(item)
       • Add a new item to the rear of the queue
     • deQueue
       • Remove the front item from the queue and return it
     • isEmpty()
       • Test to see if the queue is empty
     • isFull()
       • Test to see if the queue is full
   • Circular queue
     • When the rear pointer gets to the max value it moves to 0 if possible and then keeps going up
   • Linear queue
     • Two ways of implementation
       • As items leave the queue all the items move up a space so that the front is always the first element [0]
         • Significant processing time with a long queue
       • Pointers can be used for the start and end of the queue with an integer holding the size of the array and a variable for the current number of items in the queue
         • As more items are added and deleted there will be a gap at the front of queue where items can't be added until the rear item points to the last element of the data structure
     • Static data structures
   • Priority queue
     • Objects are ordered due to there priority first then by the time they were added to the queue

2. List

   • Operations on the list
     • isEmpty()
       • Test to see if the list is empty
     • append(item)
       • Add a new item to list to the end of the list
     • remove(item)
       • Removes the first occurrence of an item from a list
     • search(item)
       • search for an item list
     • length()
       • Returns the number of items in the list
     • index(item)
       • Returns the position of item
     • insert(pos,item)
       • Insert a new item at position pos
     • pop()
       • Remove and return the last item in the list
     • pop(pos)
       • Remove and return the item at position pos
   • Examples of lists
     • List of students in a class
     • Flights arriving at an airport

3. Stack

   • Operations on a stack
     • push(item)
       • Adds a new item to the top of the stack
     • Pop()
       • Removes and returns the top item from the stack
     • Peek()
       • Returns the top item from the stack but doesn't remove it
     • isEmpty()
       • tests to see whether the stack is empty and returns a boolean value
     • isFull()
       • test to see whether the stack is full, and returns a boolean value
   • Examples
     • Undo and redo functions
   • Last in first out (LIFO)
     • Can only add to the back and remove from the back
   • Overflow error
     • attempting to add to a full stack
   • Underflow error
     • attempting to pop from a stack that is empty
   • Calls to subroutine are executed as follows
     • The parameters are saved onto the stack
       • Local variables are saved onto the stack
         • The address to which execution returns after the end of the subroutine is reached is saved onto the stack
           • Execution is transferred to the subroutine code
   • Subroutines are executed as follows
     • The subroutine code executes
       • The return address is retrieved
         • The parameters are popped
           • Execution is transferred back to the return address
   • Stack frame for sub1
     • Local variables for sub1
     • Return address
     • Parameters for sub1

4. Hashing algorithm

   • Examples of hashing algorithms
     • Mod of a number to get an adress
       • 1024 mod 1000
         • 24 is address
     • Mid square method
       • Table size is 11 and 56 is to be stored
         • 56^2 = 3136
           • Middle 2 digits = 13
             • Address = 13 mod 11 = 2
     • Folding method
       • table size is 11 and 34721062 is to be stored
         • 34+72+10+62 = 178
           • Address = 178 mod 11 = 2
     • Hashing alphanumeric data
       • Table size is 11 and word cab to be stored
         • Convert to ASCII values
           • c= 99 a = 97 b = 98
             • 99 + 97+98 = 294
               • Address = 294 mod 11 = 8
   • Collision avoidance
     • A collision occurs when two pieces of data are attempted to be stored in the same place
     • Solutions
       • Put the item in the next available slot
         • Can lead to clustering of items in the table
       • skip value by using 1,3,5,7 etc.
   • Problems that occur
     • As the table fills up there are more and more collisions
       • Data should only take up about 50 -70% of the table size