Question

The following questions are to be done in JAVA.

1) If an array is not considered circular, the text suggests that each remove operation must shift down every remaining element of the queue. An alternative method is to postpone shifting until rear equals the last index of the array. When that situation occurs and an attempt is made to insert an element into the queue, the entire queue is shifted down so that the first element of the queue is in the first position of the array. What are the advantages of this method over performing a shift at each remove operation? What are the disadvantages?

2) what does the following code fragment do to the queue q?

ObjectStack s = new ObjuectStack();

while (!q.isEmpty())

s.push(q.remove());

while (!s.isEmpty())

q.insert(s.pop());

3)Describe how you might implement a queue using two stacks. Hint: If you push elements onto a stack and then pop them all, they appear in reverse order. If you repeat this process, they're now back in order.

Thank you for all the help.

Answer 1

1)

Advantages:

Consider a system where all the insert opeartions into the queue will be done first consequtively, and then all the remove operations will be done after that. Implementation of queue using this method will reduce un-needed swaps required in other methode performing a shift at each remove operation.

Dis-Advantages:

Consider the system where a queue is full. Now, remove and insert operations take place one by one. In this case as the array is not circular, we will have to perform a shift at each remove operation. Otherwise we can not insert new element though we have empty space into the array.

2)

Given code fragment reverses the order of elements in queue q.

Step by step:

ObjectStack s = new ObjuectStack();

while (!q.isEmpty())

s.push(q.remove()) ; // push all the elements into stack s such that end element of q is at top of s.

while (!s.isEmpty())

q.insert(s.pop()); // insert all the elements into q such that top of s is at the front of q

3)

We have to implement queue using two stacks s1 and s2. So, untill we get insert into queue requests, we keep pushing the elements into the stack s1, and when we get a remove/front request we pop all the elements from s1 and push them into s2. So now all the elements will be reversed and top of s2 will be the output.