Dispensers Flashcards
What are dispensers?
An ADT that manages a collection of data and always has a defined “current item”
How does the user manipulate the current item?
The user cannot directly manipulate the current item (changing it or doing operations it) but has to use methods that the data structure determines to manipulate the current item
What’s one implementation method to identify the current item position?
Cursors that are not public, preventing the user from directly manipulating the current item position
What are the key properties of dispensers?
- It represents a collection of data.
- It maintains a current item determined by the data structure.
- Users cannot arbitrarily modify the current item.
- Modification of the current item occurs through specific operations defined by the dispenser (e.g., push, pop, enqueue, dequeue).
What are stacks and queues considered in terms of lists?
lists with restricted functionality; utilise a subset of list operations
What is a restriction?
A class (e.g., stack) that contains an instance variable of a more functional class (e.g., list). The less functional class exposes only the necessary operations from the more functional class through its public interface.
What is a heap?
A type of dispenser implemented as a binary tree with a specific property called the heap property: the item stored at a node must be at least as large as any of its descendants
Where is a heap’s current item?
At the root of the tree
What are essential heap operations?
- insert
- delete
What is the point of having a Dispenser? (Like being able to utilize Stack on Linked and Arrayed Lists)
Common functionality is in base class - since the ArrayedList and LinkedList share the same interface, the logic for the stack methods are identical for the two versions of the stack. Hence,
- Software maintenance (in one class, Stack Class) and implementation are easier
- Functionality of two different flavours of stack without having to code any new data structures
Steps for insertion into a heap
- Place the added node to the lowest right of the tree while keeping all of the lowest level of nodes to the left
- Check if the parent of the added node is smaller than the added node
- If it is, switch the positions of the added node and its parent node
- Continue switching until the added node’s parent node is bigger than the added node
Steps for deletion into a heap
- Remove the root node and place the node on the far right of the lower level in the position of the root node
- Check if either children of the root node is bigger than the new root node
- Switch spots with the child that is bigger than the new root node
- If both child nodes are bigger than the root node, switch spots with the biggest child node
- Keep switching spots until both children are smaller
