Question

A Deque is an ADT which allows efficient (O(1)) insertion and removal at either end of the structure. Typically, a deque is implemented with a doubly-linked list (DLL), and has the following API:

addFront(data)  # adds element to head of the DLL
removeFront()   # removes (and returns) element from head of the DLL
addRear(data)   # adds element to the tail of the DLL
removeRear()    # removes (and returns) element from the tail of the DLL

Which of the Deque operations could be used to implement the Queue ADT enqueue and dequeue methods, respectively:

A deque cannot be used to implement a queue

addFront, removeFront

addFront, removeRear

addRear, removeFront

(addFront, removeRear) or (addRear, removeFront)

addRear, removeRear

(addFront, removeFront) or (addRear, removeRear)

Answer 1

As Deque as Defined in Question it self that we can insert and delete Both sides.

Front Side Known as : Head(front pointer)

Back Side Know as : Tail (rear pointer)

So, In Order to make Deque as Queue , Let's understand Queue's functionality first.

Queue : It is a data-structure that works in passion of FIFO(first in first out). Like copy-paste works(it uses Queue).

Now, there is two operation inside this.

Enqueue : Intsert a element into Queue.

Dequeue : Delete element from Queue.

From above Options , Let's evaluate them One by One-->>

1. addFront, removeFront------------------>>Rejected
2. addFront, removeRear--------------------->>> Selected
3. addRear, removeFront ------------------>> Selected
4. (addFront, removeRear) or (addRear, removeFront)---->>Selected
5.addRear, removeRear----------->> Rejected
6.(addFront, removeFront) or (addRear, removeRear) --->> Rejected

So as we can see the Best option is 4.

We can insert from Front and delete from Rear or can insert from Rear and delete from Front.

So, (addFront, removeRear) or (addRear, removeFront) are valid for implemention of Queue from Deque.

Void Enqueue(x) :: To enqueue an element x in the Queue, add element at front of Deque.

Integer Dequeue() :: To dequeue an element from Queue, remove element at rear of Deque and return it.

Time Complexity for Both Operation WIll be O(1).