Algorithms for the main data structures
No description yet. This curated deck is ready for daily study.
Card preview (14)
Are stacks FIFO or FILO?
FILO
Which function adds an item to a stack?
Push
Which function removes an element from a stack?
Pop
What is the significance of the back pointer in the array representation of a queue?
Holds the location of the next available space in the queue
Which function returns an item at the front of a queue without removing it?
Peek
What is the purpose of the front pointer in the array representation of a queue?
Points to the space containing the first item in the queue
What value is the top pointer initialised to in the array representation of a stack?
-1
Give pseudocode for the two functions which add new elements to stacks and queues
Stacks: push(element) top += 1 A[top] = element Queues: enqueue(element) A[back] = element back += 1
Which function returns the item at the top of a stack without removing it?
Peek
What is a linked list?
• Composed of nodes, each of which has a pointer to the next item in the list • First item in a list is referred to as the head and the last as the tail
What is a tree?
• Formed from nodes and edges • Cannot contain cycles and aren’t directed • Useful as a data structure because they can be traversed
What is meant by depth first (post-order) traversal?
• Depth first search goes as far down into the tree as possible before backtracking • The algorithm uses a stack and goes to the left child node of the current node when it can • If there is no left child then the algorithm goes to the right child. • If there are no child nodes, the algorithm visits the current node, outputting the value of the node before backtracking to the next node on the stack and moving right
What is meany by breadth-first?
• Starting from the left, breadth-first visits all children of the start node • The algorithm then visits all nodes directly connected to each of those nodes in turn, continuing until every node has been visited (uses a queue) • E.g. 5,3,8,2,4
What is meant by pre/post/in-order?
• Post-order: line passes to the right of the nodes • Pre-order: line passes to the left of the nodes • In-order: line passes under the nodes