Topc 5 ADT Flashcards
ADT
Abstract Data types
What are ADT’s? (Examples)
2D Arrays Linked List Stacks Queues Trees
Characteristics of stacks (3)
Vertical Last in; first out (LIFO) Collections (Unknown size; don’t know if it’s sorted)
Adding an element to a stack
.push()
Removing an element from a stack
.pop()
Reverse collection pseudocode
// declare an empty stack int count = 0 loop while collection.hasNext() stack.push(collection.getNext() ) count ++; end loop loop i from 0 to count-1 newarray[i] = stack.pop() end loop
Characteristics of a Queue
Horizontal First in; first out (FIFO)
Array to Stack pseudocode
loop i from 0 to array.length-1 S.push(array[i]) end loop (same can be done with queues; except enqueue)
Printing out a stack pseudocode
loop while not stack.isEmpty() output( stack.pop() ) end loop
Adding an item to a Queue
.enqueue()
Removing an item from a Queue
.dequeue()
Real world examples of a Queue
Printer Queues Supermarket Queues
Static (3)
Size determined at creation Not good use of memory space For loops
Dynamic (4)
Changes size Nodes and pointers Good use of memory space While loops
Accessing element in 2D arrays
array[row][column]
Declaring 2D array example
int [ ] num = new int [row][col]
Finding the number of rows
array.length
Averaging an array pseudocode
int count = 0; int average = 0; int total = 0; loop i from 0 to array.length-1; count = count + array[i]; total ++; end loop average = count / total;
Finding the number of columns
array[0].length
Recursion
A method that calls itself in a program; which becomes more simple and stops calling itself at some stage
Constructing a binary search tree
- Initial value 2. Second value greater than initial = right 3. Second value less than initial = left
Root pointer
Top most element in the tree
Subtrees
Point either left or right
Null pointer
Points to no elements
Types of linked lists
Singly; Singly circular and Doubly linked list
Parent
Node that has children
Leaf
Node with no children
Full binary tree
Each node has 0 or 2 children
Preorder
Left
Inorder
Bottom
Postorder
Right
Best use of stack
Implementing function calls
Best uses of queues
Computing applications (E.g. CPU) Buffers Playlist Interrupt handling (C; B; P; I)
Best uses of linked list (2)
Unknown size Want to insert and delete from anywhere
Best uses of arrays
Random access to elements Speed when iterating
Best uses of binary trees
Binary Search Tree Heap (Priority Queues) GGM Trees Syntax tree
Binary tree vs singly linked list
Binary tree - More storage; 2 pointers; Binary search can be used and more efficient Singly linked list - Less storage; 1 pointer; Linear search (slower) and less efficient
Stacks and recursion
Recursive calls involves use of stacks - storing; popping and pushing
Advantages of making a queue dynamic
No pre determined/ fixed size Efficient use of memory
