Deques in Python

Luckily, collections.deque has been designed in Python, which have fast appends and pops from both ends.

from collections import deque
q = deque(['structures', 'is'])
q.append('fun') # add_last
q.append('!') # add_last
q.appendleft('data') # add_first
q.pop() # delete_last
print(q)
q.popleft() # delete_first
print(q)

As we can see, append() is to add to the end, while appendleft() is to add to the front; pop() is to remove the last, while popleft() is to remove the first.

Deques based on circular arrays

In practice, collections.deque is always your top choice. But as for learning, it is meaningful and interesting to implement a deque on our own. The complete code can be found at array_deque.py.

class ArrayDeque:
    """A double-ended queue (deque) based on circular queues."""

    DEFAULT_CAPACITY = 10

    def __init__(self):
        self._data = [None] * ArrayDeque.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

Clearly, add_last() is exactly the same with enqueue(), and remove_first() is exactly the same with dequeue().

As for as_first() and delete_last(), we rely on mod to circularly decrement the index¹:

def add_first(self, item):
    if self.size() == len(self._data):
        self._resize(2 * len(self._data))
    self._front = (self._front - 1) % len(self._data)
    self._data[self._front] = item
    self._size += 1

def delete_last(self):
    if self.is_empty():
        raise NoElement('Remove from empty queue!')
    if self.size() == len(self._data) // 4:
        self._resize(len(self._data) // 2)
    back = (self._front + self._size - 1) % len(self._data)
    answer = self._data[back]
    self._data[back] = None
    self._size -= 1
    return answer

Application: number of recent calls

This application is from leetcode, and readers shall check the question description by themselves.

As for this problem, one feasible algorithm is to use deque:

from collections import deque


class RecentCounter:
    def __init__(self):
        self.data = deque()

    def ping(self, t: int) -> int:
        while len(self.data) > 0 and (t - 3000) > self.data[0]:
            self.data.popleft()
        self.data.append(t)
        return len(self.data)

¹ -1 mod n = n - 1.