ASAP: Choose the appropriate data structures: array, linked list, stack, queue o
ID: 3582918 • Letter: A
Question
ASAP: Choose the appropriate data structures: array, linked list, stack, queue or tree in these situations (can choose 0 or more than 1):
1. Print paper requests to printer
2. Store social network feeds, do not know size but can add things dynamically
3. Trace the ways in a maze by using paint. If you reach the dead end, you retrace the steps and delete the paint.
4. Store possive moves in a chess game, you can look ahead 4-5 turns, consider possible sequences of moves
5. Implement the back button in Internet browser.
Explanation / Answer
Ans.1 Stack: Printer prints sequentially. Therefore, all the print requests have to be put in a stack. As and when a request gets executed, it gets popped out.
Ans.2. Linked List: Since one feed is linked to many feeds, it can have various pointers pointing at the single news feed. This will reduce the space and would be easily accessible.
Ans.3. Tree: Since a maze may have many solutions (leaves) and only one starting point (root), we can apply bfs or dfs on the tree to find the exact path.
Ans.4. Tree: Each move leads to a possible set of moves. So, we can again use BFS or DFS to retrace back to original move if we moved accidentally.
Ans.5. Stack: Since, we go from one page to other, we can have a stack to store the current page (top of the stack). When we move backwards, the top would be popped.