Data Structures (4.2 - Part 2) Flashcards
Stack
Data structure where items are always added/removed from top
What type of data structure is stack?
FILO
2 data structures which can be used to implement stacks
Arrays and linked lists
push ()
Adds item to top of stack
pop ()
Removes and displays item at top of stack
peek ()
Displays item at top of stack without removing it
isEmpty ()
Checks to see if stack is empty
isFull ()
Checks to see it stack is full
When do stack overflows occur?
When attempting to push item onto stack that is already full
In which type of stacks do overflows occur?
Static
How do trees represent data?
Hierarchically
2 rules for creating trees
- Each node must be connected to 1 parent node and 1 or more children
- There should be no direct connections between nodes on same level of hierarchy
3 ways to traverse tree structure
- Pre-order
- In-order
- Post-order
Pre-order traversal
Starts from root node and visits all following nodes from left to right
In-order traversal
Starts with nodes on left subtree, then visits root node and then goes to right subtree
Post-order traversal
Starts with left subtree (from bottom to top), then goes to right subtree (also bottom to top) and finishes at root node
Binary search tree
Tree data structure used for efficient searching of data
Difference between binary search trees and trees
Binary search trees can have no more than 2 child nodes
When does binary search tree store child node to left side?
When node is less than other node
When does binary search tree store child node to right side?
When node is greater than other noe
