Logout

D.4.14

Outline the features of ADT’s stack, queue and binary tree.

 

Teaching Note:

Students should be able to provide diagrams, applications and descriptions of these ADTs. For example, they should know that a binary tree can be used to efficiently store and retrieve unique keys.

 

Sample Question:

sdfsdfsf

JSR Notes:


Features of Stack ADT:

- queues are made of a "chain" of self-referencing nodes

- items can be added, or "pushed" onto the "tail" end of the stack

- items can be taken from, or "popped" from the "tail" of the stack, and so operating in a LIFO basis

- checks can be made to see if the stack is empty, thus preventing the error of trying to access something that is not there

Features of Queue ADT:

- queues are made of a "chain" of self-referencing nodes

- items can be added, or "enqueued" at the front, or in front of the "head" of the queue

- items can be taken from, or "dequeued" from the front of the queue, and so operating in a FIFO basis

- checks can be made to see if the queue is empty, thus preventing the error of trying to access something that is not there

Features of Binary Tree ADT:

- that tree is made of nodes which have two pointers each: a pointer pointing to the right of the node to items "greater" than it, and one pointing to the left of the node to items "lesser" than it

- the tree starts assembling itself with a "root" node (which, to have a balanced tree, should be a "middle" value of the set)

- items are added by progressing down through the tree, asking at each node whether they are "greater than" or "lesser than" the current node, and then being attached when they get to the "end of the line"

- because of the way values are added, they are naturally sorted

- searching can be done in a binary way, because of this natural sorting process, since at every step through the binary tree when searching, half of the remaining nodes are eliminated from the search

- through various algorithms, nodes may be effectively deleted from the tree by re-linking nodes around them