Abstract Data Types
I am going to talk about ADTs in this post because I found ADTs the most difficult topic to grasp so far. The ADTs we have covered in this course are stacks, queues, trees and binary search trees.
Stacks are ADTs representing piles of items. Stacks have a top and a base. Items can only removed and added from the top of the stack. The last item to be added to the stack will always be the first item removed from the stack. Common functions used with stacks are pop, push and is_empty. Pop removes the first item at the top of the stack. Push adds an item at the top of the stack. Is_empty returns weather or not the stack contains any items. No items can be removed from empty stacks.
Queues are ADTs that are similar to stacks. However, when an item is removed (or popped) from a queue, it is removed from the beginning of the queue; the first item in is the first item out. When an item is added (or pushed) to a queue, it is added at the end of the queue; so the last item in is the last item out. A queue is therefore a sequence instead of a pile of items.
Trees are ADTs containing sets of nodes. Nodes, beginning with the root of the tree, are connected by edges. All nodes have parent nodes except for the root. Nodes can have children (other nodes rooted from that node). If a node has no children, it is named a leaf. Trees have specific heights. The height of the tree is the longest sequence of nodes.
Binary Search Trees (BSTs) are ADTs that differ only in one aspect to Trees. This difference is that in BSTs, nodes may only contain two children.
With recursion, information from any of these ADTs, is very easily accessed. Recursion is specially useful when dealing with trees and binary search trees because children nodes can be accessed through parent nodes. I find it simple to create running functions that obtain data form each of these ADTs. I still have trouble however, understanding how the computer reads these ADTs when running recursion functions.
