deque

ArrayDeque.py

class EmptyException(Exception):
    pass

class ArrayDeque:
    # class varriable
    DEFAULT_CAPACITY = 10

    def __init__(self, capacity=DEFAULT_CAPACITY):
        self._data = [None] * capacity
        self._front = 0
        self._rear = 0

    def __str__(self):
        return "front : " + str(self._front)  \
                          + "\nrear : "       \
                          + str(self._rear)   \
                          + "\ndata : "       \
                          + str(self._data)

    def __len__(self):
        return self._rear - self._front

    def is_empty(self):
        return self._rear == self._front
    
    def first(self):
        self._EMPTYCHECK()
        return self._data[self._front]
    
    def last(self):
        self._EMPTYCHECK()
        return self._data[self._rear]

    def delete_first(self):
        self._EMPTYCHECK()
        elem = self._data[self._front]
        self._data[self._front] = None

        self._front += 1
        return elem
    
    def delete_last(self):
        self._EMPTYCHECK()
        elem = self._data[self._rear]
        self._data[self._rear] = None

        self._rear -= 1
        return elem
    
    def add_first(self, e):
        if self._front == 0:
            self._append_left()

        self._front -= 1
        self._data[self._front] = e
        
    def add_last(self, e):
        if self._rear == len(self) - 1:
            self._append_right()

        self._rear += 1
        self._data[self._rear] = e
        

    # private method
    def _append_left(self):
        length = len(self._data)
        new_data = [None] * length * 2
        for i in range(length):
            new_data[length + i] = self._data[i]
        self._front += length
        self._rear += length
        self._data = new_data

    def _append_right(self):
        length = len(self._data)
        new_data = [None] * length * 2
        for i in range(length):
            new_data[i] = self._data[i]
        self._data = new_data

    # private assert
    def _EMPTYCHECK(self):
        if self.is_empty():
            raise EmptyException('Deque is Empty')
        
s = ArrayDeque()

s.add_last(1)
print(s)
s.add_last(3)
print(s)
s.add_first(4)
print(s)
s.delete_first()
print(s)