2.3.1 Algorithms for the Main Data Structure

Question 1

What is a stack?

Answer 1

• First in, last out data structure
• Implemented as array and use single pointer
• Points to element at top of stack

Question 2

What are the stack operations?

Answer 2

• size() - check size
• isEpty() - check if empty
• peek()- return top element
• push(element)- add to stack
• pop() - remove and return top element

Question 3

What are queues?

Answer 3

• First in first out data structure
• Represented as array
• Two pointers
• One holds position of first element, the other the next available space

Question 4

What are the queue operations?

Answer 4

• size()- check size
• isEmpty()- check if empty
• peek()- return front element
• enqueue(element) - add to the queue
• dequeue - remove and return front element

Question 5

What are linked lists?

Answer 5

• Abstract, dynamic data structure to hold ordered data from different locations
• Composed of nodes each of which has a pointer to the next item in the list
• First item in the head
• Last item is the tail

Question 6

How do you insert an item into a linked list?

Answer 6

• Add item to next free space
• Follow pointers from start until you find a node greater than the item
• Change pointer of previous node to point to item
• Change the pointer of the item to point to the next node

Question 7

What are trees?

Answer 7

• Formed from nodes and edges
• Cannot contain cycles
• Undirected
• Useful dta structure as can be traveresed

Question 8

What are the types of tree traversal?

Answer 8

• Depth first (post-order) traversal
• Breadth first

Question 9

How do you perform post-order traversal?

Answer 9

• Draw line starting to left of root
• Draw a bubble aroyund the tree
• Output as the line passes to the right of a node
• Implemented using a stack

Question 10

How do you perform breadth first traversal?

Answer 10

• Visits all children of the start node
• VIsits all nodes directly connected to each of those nodes in turn
• Implemented using a queue