Question

5) Assuming that the following items are stored in a double ended queue called myDeque: 2, 3, 1, 0, -1. Draw memory diagrams showing how moveToBack method will change the pointers (step-by-step) for the following scenarios - each scenario starts with the original content of the queue:
1. myDeque.moveToBack(3) - the content of myDeque is now: 2 1 0 -1 3

2. myDeque.moveToBack(1) - the content of myDeque is now: 2 3 0 -1 1

3. myDeque.moveToBack(-1) - the content of myDeque is now: 2 3 1 0 -1

4. myDeque.moveToBack(5) - the content of myDeque is now: 2 3 1 0 -1

Answer 1

The original contect of the myDeque is as follows:

2

3

1

0

-1

^Front ^Rear

moveToBack(component c): This method moves c to the back of the queue, where c is the component to be moved.

Deque (Double ended queue) can be implemented in 2 ways - Linked list deque and Dynamic array queue

1. myDeque.moveToBack(3)

Here I am implementing this in Linked list Deque.

In linked list deque each node has pointer to the next node, when 3 is pushed back, the pointer pointing to 3 now points to the next value in queue and rear node pointer points to value which is pushed back i.e. 3 in our case.

2. myDeque.moveToBack(1)

Here I am implementing it in Dynamic array queue, this directly moves the values to the front stack when a value is removed. So the value 0, -1 are moved to the corresponding front stacks and 1 to the rear end.

3. myDeque.moveToBack(-1)

Here alreay -1 is in the rear end, when it tries to puch -1 to rear end. The rear end pointer is already pointing to -1. So no change in Deque.

2

3

1

0

-1

4. myDeque.moveToBack(5)

In this case it tries to find value 5, when it fails to find this value throws an error. But the Deque remains unchanged.

2

3

1

0

-1