Question $1$: In Fixed Size Array, maximum number of elements is fixed. It will have the following signature.

Class FixedSizeArray:

def $\_\_$init$\_\_($self$,$ N$)$: $//$ N is the maximum number of items

self.data $=[$None$]*$N

self.length $=0$

self.capacity $=$ N

def insertAt$($self$,$ index, value$)$: $//$ insert data item $($value$)$ at a particular position $($index$).$

def remove$($self$,$ index$)$: $//$ remove data item from a particular position $($index$).$

def printArray$($self$)$: $//$ print the content of the array.

def length$($self$)$: $//$ return the number of data items in the list.

Note: You cannot use the insert, append, or pop function in the python list. Only, way you can update the

content of the list is through an assignment operation on a certain index position. For example: self.data$[$i$]$

$=$ value or self.data$[$i $+1]=$ self.data$[$i$].$ Use the following constructor for the Deque class, where n is the

maximum size of the deque object. The maximum size of the deque would be already known.

Question $2$: Now, use your implemented FixedSizeArray class from question $1$ to develop a Dequeue class

that will offer all the functionalities of traditional dequeue data structure with the property that the data

items can be added and removed both from the front and back. Dequeue class will use an instance of

FixedSizeArray to store items with the following structure.

Class Deque:

def $\_\_$init$\_\_($self$,$ n$)$:

self.array $=$ FixedSizeArray$($n$)$

self.first $=0//$it can be something else too based on your implementation

self.last $=0//$it can be something else too based on your implementation

This class needs to have the following functions implemented.

$$ add$\_$first$($e$)$: Add element e to the front of deque.

$$ add$\_$last$($e$)$: Add element e to the back of deque.

$$ delete$\_$first$()$: Remove and return the first element from deque; an error occurs if the deque is

empty.

$$ delete$\_$last$()$: Remove and return the last element from deque; an error occurs if the deque is

empty.

$$ first$()$: Return $($but do not remove$)$ the first element of deque; an error occurs if the deque is

empty.

$$ last$()$: Return $($but do not remove$)$ the last deque element; an error occurs if the deque is empty.

$$ is$\_$empty$()$: Return True if deque does not contain any elements.

$$ length$()$: Return the number of elements in the deque.

$$ print$\_$deque$()$: Prints all the items currently present in the deque from the first inserted item to

the last one. Note: this function does not remove any item from the internal list.

Question $3$: Write codes to create an instance of the Deque class $($D $=$ Deque$(10))$ and perform the

following operations in this sequence with the Deque object D:

$1.$ D$.$delete$\_$last$()$

$2.$ D$.$add$\_$last$(50)$

$3.$ D$.$add$\_$first$(2)$

$4.$ D$.$delete$\_$last$()$

$5.$ D$.$print$\_$deque$()$

$6.$ D$.$add$\_$first$(10)$

$7.$ D$.$add$\_$first$(100)$

$8.$ D$.$add$\_$last$(1)$

$9.$ D$.$delete$\_$last$()$

$10.$ D$.$delete$\_$first$()$

$11.$ D$.$length$()$

$12.$ D$.$print$\_$deque$()$

Question $4$: Find out the big$-$oh notations of your developed algorithms in the Stack and Deque class for

the following functions:

$1.$ insertAt$($index$,$ value$)$

$2.$ remove$($index$)$

$3.$ add$\_$first$($e$)$

$4.$ add$\_$last$($e$)$

$5.$ delete$\_$first$()$

$6.$ delete$\_$last$()$