PYTHON PROGRAM

Complete ArrayDeque implementation of the double-ended queue ADT as shown in Section.

SCREENSHOT SAMPLE OUTPUT AS WELL.

Complete ArrayDeque implementation of the double-ended queue ADT as shown in Section

3.2 Implementing a Deque with a Circular Array We can implement the deque ADT in much the same way as the ArrayQueue class provided in Code Fragments 6.6 and 6.7 of Section 6.2.2 (so much so that we leave the details of an ArrayDeque implementation to Exercise P-6.32). We recommend maintaining the same three instance variables: _data, _size, and _front. Whenever we need to know the index of the back of the deque, or the first available slot beyond the back of the deque, we use modular arithmetic for the computation. For example, our implementation of the last() method uses the index back (self._front + self._size 1) % len(self._data) Our implementation of the ArrayDeque.add-last method is essentially the same as that for ArrayQueue.enqueue, including the reliance on a _resize utility. Like- wise, the implementation of the ArrayDeque.delete_first method is the same as ArrayQueue.dequeue. Implementations of add_first and delete_last use similar techniques. One subtlety is that a call to add_first may need to wrap around the beginning of the array, so we rely on modular arithmetic to circularly decrement the index, as self._front (self._front 1) % len(self._data) #cyclic shift The efficiency of an ArrayDeque is similar to that of an ArrayQueue, with all operations having O(1) running time, but with that bound being amortized for op- erations that may change the size of the underlying list. =