- Deque: This would be a decent choice, since you can add/remove from both the front/end of the line in O(1) time, and the number of patients can be kept track of with an integer variable, so getting the size of the line would be O(1). You can also ensure a max capacity of N by checking the size of the line before you add a patient.
- Array: Since you need to add to the beginning of the line, a normal array would not be a good choice since you’d have to shift all elements over by 1 position to make room at the beginning of the array. This would give you O(n) for adding to the front of the line.
- Circular Array: This would be the best choice, better than the deque for one small reason… since it has an underlying array, all of the memory locations (spots for patients in line) are contiguous, whereas with a dequeue, which is implemented with an underlying linked list, the memory locations are random and not contiguous. This provides a small benefit. You could create an array of size N (the capacity of the hospital) and use the same memory locations over and over. If there was no capacity for the hospital (unlimited # of patients can be in line), you would however need to use a dequeue (since an array has a set length). Adding/removing from the front/back is O(1) just like with the deque, and getting the size of the line is also O(1) since you can calculate it using the start/end indexes of the line.
- Array + Stack: This would offer no benefit over just an array (#2), since the stack is useless (see #5).
- Stack: Since you need to add to both the beginning and end of the line, a stack would not work (it can only add to one side).
So in order of best to worst: 3, 1, 2, 4, 5.
All are possible to use, except for #5.
2
solved Java Data Structures (Most Efficient Structure For Specific Program) [closed]