Answer to Question #146461 in Programming & Computer Science for Joshua

Question

The following sequence of operations are performed on an empty Queue Q: ADD(1,Q), ADD(2,Q), REMOVE(Q), ADD(1,Q), ADD(2,Q), REMOVE(Q), REMOVE(Q), REMOVE(Q), ADD(2,Q), REMOVE(Q). The sequence of the removed values are?
a.2,1,2,2,1
b.2,1,2,2,2
c.2,2,1,1,2
d.1,2,1,2,2

Answer 1

When working with Queue, we should remember that we insert the elements at the end of the Queue and remove them from the beginning of the Queue. Let's consider step-by-step the sequence of operations that are performed on an empty Queue Q:

1) ADD(1,Q), ADD(2,Q) - at this step we add to empty Queue two elements (1, 2), so we

have the following Queue: (1, 2);

2) REMOVE(Q) - at this step we remove the first element located at the head of Queue (1)

and then we have the following Queue: (2);

3) ADD(1,Q), ADD(2,Q) - at this step we add two new elements at the tail of Queue, and Queue

looks like: (2, 1, 2);

4) REMOVE(Q), REMOVE(Q), REMOVE(Q) - at this step we consistently remove elements located at the head of Queue (2, 1, 2) and Queue becomes empty;

5) ADD(2,Q), REMOVE(Q) - at this step we add to empty Queue one element (2) and then remove it.

Finally, we have the following sequence of the removed values: 1, 2, 1, 2, 2.

Therefore, the answer is d)

Answer:

d.1,2,1,2,2