Data Structures: Stacks, Queues, and Trees
Practice core operations and use cases for common data structures
Data Structures: Stacks, Queues, and Trees
Practice core operations and use cases for common data structures
CS - Grade 9-12
- 1
A stack starts empty. The operations are push(4), push(9), push(2), pop(), push(7), pop(). What values are removed by the two pop operations, in order, and what remains in the stack from bottom to top?
A stack uses last in, first out behavior.
The first pop removes 2, and the second pop removes 7. The remaining stack from bottom to top is 4, 9. - 2
A queue starts empty. The operations are enqueue(A), enqueue(B), enqueue(C), dequeue(), enqueue(D), dequeue(). What values are removed by the two dequeue operations, in order, and what remains in the queue from front to back?
The first dequeue removes A, and the second dequeue removes B. The remaining queue from front to back is C, D. - 3
Explain the difference between LIFO and FIFO. Name one data structure that uses each rule.
Think about a stack of plates and a line of people waiting.
LIFO means last in, first out, and a stack uses this rule. FIFO means first in, first out, and a queue uses this rule. - 4
A program checks whether parentheses are balanced in the expression (a + b) * (c + d). Which data structure is best for tracking the opening parentheses, and why?
A stack is best because each closing parenthesis should match the most recent unmatched opening parenthesis. - 5
A printer receives jobs in the order Job1, Job2, Job3, and Job4. If the printer processes jobs in the order they arrive, which data structure should manage the jobs? What job is processed first?
Printers usually serve the earliest waiting job first.
A queue should manage the jobs because it processes items first in, first out. Job1 is processed first. - 6
Draw or describe the binary tree with root 10, left child 5, right child 15, left child of 5 equal to 2, and right child of 5 equal to 7. Then list the leaf nodes.
The root is 10, with children 5 and 15. Node 5 has children 2 and 7. The leaf nodes are 2, 7, and 15 because they have no children. - 7
For the binary tree with root A, left child B, right child C, left child of B equal to D, and right child of B equal to E, write the preorder traversal.
Preorder means root, left, right.
The preorder traversal is A, B, D, E, C because preorder visits the root first, then the left subtree, then the right subtree. - 8
For the binary tree with root A, left child B, right child C, left child of B equal to D, and right child of B equal to E, write the inorder traversal.
The inorder traversal is D, B, E, A, C because inorder visits the left subtree, then the root, then the right subtree. - 9
For the binary search tree containing the values 8, 3, 10, 1, 6, 14, 4, 7, and 13, list the values in sorted order using an inorder traversal.
In a binary search tree, smaller values are on the left and larger values are on the right.
The values in sorted order are 1, 3, 4, 6, 7, 8, 10, 13, 14. An inorder traversal of a binary search tree visits values from smallest to largest. - 10
A binary search tree is empty. Insert the values 12, 5, 18, 2, 9, and 15 in that order. What are the left and right children of 12?
The left child of 12 is 5, and the right child of 12 is 18. Values less than 12 go to the left side, and values greater than 12 go to the right side. - 11
Choose the best data structure for an undo feature in a text editor: stack, queue, or tree. Explain your choice.
The last edit you made is usually the first edit you want to undo.
A stack is the best choice because the most recent action should be undone first. This matches last in, first out behavior. - 12
A customer service system must help customers in the same order they joined the waiting list. Choose the best data structure and explain what operation adds a customer and what operation serves a customer.
A queue is the best data structure because customers should be helped first in, first out. Enqueue adds a customer, and dequeue serves a customer.