(Solved): A dequeue is a data structure that represents an ordered list of items. It allows access to both en ...

A dequeue is a data structure that represents an ordered list of items. It allows access to both ends (front and back) of the list. Specifically, it supports the following operations: - d.isEmpty (): return true if the dequeue is empty - d.addFront $(x)$ : add $x$ to the front of the dequeue - d.removeFront (): remove and return the element at the front of the dequeue - d.addBack $(x)$ : add $x$ to the back of the dequeue - d.removeBack(): remove and return the element at the back of the dequeue A stack is a similar data structure that only allows the following operations: - s.isEmpty(): return true if the stack is empty - s.push $(x)$ : add $x$ to the stack - s.pop(): remove and return the top element of the stack Design a dequeue using three stacks, with $O(1)$ amortized time per operation. For each of the five dequeue operations, provide a brief explanation of your approach and present pseudo-code with relevant comments. (Note: Your data structure can maintain additional bookkeeping information, such as the number of elements in the dequeue. But it should not make use of an array or other data structures to store the data in the dequeue.)