COSC 2320 Chapter 25-31: Chapter 25-31

5 Pages
Unlock Document

University of Houston
Computer Science
COSC 2320
Hilford Victoria

Chapter 25-31 Ch.25: Stacked abstract data type (ADT)  Zybook notes o Stack – items are only inserted on or removed from the top of a stack  Stack is last-in first-out o Push – inserts an item on top of stack o Pop – removes and returns the item on top of the stack o Operations  Push(stack, x)  insert x on top of stack  Pop(stack)  returns and removes item top of stack  Peek(stack)  Return but does not remove item at top of stack  IsEmpty(stack)  Returns true if stack is empty  GetLength(stack)  Return number of items in stack Ch.27: Queue (ADT)  Zybook notes o Queue – items are inserted at the end of the queue and removed from the front of the queue  First-in first-out o Push – inserts an item at the end of the queue o Pop – removes and returns the item at the front of the queue o Operations  Push(queue, x)  Insert x at end of the queue  Pop(queue)  Returns and removes item at front of queue  Should not be applied to an empty queue  Peek(queue)  Returns but does not remove item at the front of the queue  Should not be applied to an empty queue  IsEmpty(queue)  Returns true if queue has no items  GetLength(queue)  Returns the number of items in the queue o Queue linked lists  Head node = queue front  Tail node = queue end  Popping is performed by pointing a local variable to the list’s head node  Removing the head node from the list o Then returning the local variable Ch.29: Hash Tables  Zybook notes o Hash table – stores unordered items by mapping (hashing) each item to a location in an array  Searching/inserting/removing an item may require only O(1) instead of O(N) for searching a list or O(logN) for binary search o Key – value used to map to an index  Key should be unique o Bucket – array element from a hash table o Hash function – computes a bucket index from the item’s key  (Num key) / (num buckets) = keys to each bucket o Collision – when an item being inserted into a hash table maps to the same bucket as an existing item in the hash table o Chaining – handles collisions by using a list for each bucket  If an item collides with another  Item is added in the bucket as a list Ch.31: Linear probing  Zybook notes o Linear probing – handles a collision by starting at the key’s mapped
More Less

Related notes for COSC 2320

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.