Please help in Java!! array is not considered circular, the text suggests that e
ID: 3588053 • Letter: P
Question
Please help in Java!!
array is not considered circular, the text suggests that each remove 2. If an 0eration must shift down every remainingelement of a queue. An alternative entire queue is shifted down so that the first element of the queue is in the ming a shift at each remove operation? What are the disadvantages? thod is to postpone shifting until rear equals the last index of the array. When situation occurs and an attempt is made to insert an element into the queue, met first position of the array. What are the advantages of this method over perfoExplanation / Answer
Two methods are available for deque :
Method 1 : "Remove operation must shift down every remaining element of a queue"
In this method we have two pointers [or indexes]
1. front - [hold index of position from where element will be deleted.]
2. rear - [hold index of position where element will be inserted]
Initially when Queue is empty, front index will be -1 [because there is no element to be removed] and rear will be 0 [position where element will be inserted]
After inserting element 1 in the queue, front changes to 0 and rear will be shifted by 1 i.e 2.
Imagine 1 million items has been added to queue.
i.e front is still 0 and rear is now 1000000 [i.e 1 million]
When an element is to be removed, the element will be removed from the front. But then all the elements will be shifted toward left.
JUST THINK OF THE OPERATIONS IT REQUIRES IN THIS CASE ? I guess you can imagine it.
Yes you are right.
It requires 999999 operations to make a shift to left.
The problem with this implementation is that the time complexity to delete element from Queue is O(n). Ideally inserting an element in queue and removing an element from queue should take constant time. So this is not the right kind of implementation.
Method 2 : "Postpone shift"
In this case as soon as you remove first element, we just need to increase the front by 1. i.e only one operation.
Shifting will be postponed till REAR value is same as Array last index.
Conclusion : Method 2 is highly preferable. Method 1 is just easy to implement but not of much use.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.