0%

Python Underlying Implementation for Deque

Posted on Edited on In
Python underlying implementation for deque

Deque is the abbreviation of double-ended queue. Since we can modify the deque on both sides, it could be used for implementing stack and queue.

The underlying implementation for deque is beautiful, from my perspective. We can image a deque as a double-ended linked list. Each container/node/block stores a separate fixed size array/list and points two pointer to its left and right block. Meanwhile, the container should maintain a index array to store the first address.

​ source_link

Python source code: link

Cpython source code: link

I have designed an implementation of deque.

1
2
3
4
5
6
7
8
9
class MyCircularDeque:
  def __init__(self, k: int):
      """
      Initialize your data structure here. Set the size of the deque to be k.
      """
      self.maxlength = k
      self.deque  = [None] * 2 * k
      self.left = k // 2 + 1
      self.right = k // 2
1
2
3
4
5
6
7
8
9
10
11
12
13
def insertFront(self, value: int) -> bool:
    """
    Adds an item at the front of Deque. Return true if the operation is successful.
    """
    if self.right - self.left < self.maxlength - 1:
        if self.left == 0:
            newblock = [None] * len(self.deque)
            self.deuqe = newblock + self.deque
        self.left -= 1
        self.deque[self.left] = value
        return True
    else:
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
def insertLast(self, value: int) -> bool:
    """
    Adds an item at the rear of Deque. Return true if the operation is successful.
    """
    if self.right - self.left < self.maxlength - 1:
        if self.right == len(self.deque) - 1:
            newblock = [None] * len(self.deque)
            self.deque = self.deque + newblock
        self.right += 1
        self.deque[self.right] = value
        return True
    else:
        return False
1
2
3
4
5
6
7
8
9
def deleteFront(self) -> bool:
    """
    Deletes an item from the front of Deque. Return true if the operation is successful.
    """
    if self.isEmpty():
        return False
    self.deque[self.left] = None
    self.left += 1
    return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def deleteLast(self) -> bool:
    """
    Deletes an item from the rear of Deque. Return true if the operation is successful.
    """
    if self.isEmpty():
        return False
    self.deque[self.right] = None
    self.right -= 1
    return True

def getFront(self) -> int:
    """
    Get the front item from the deque.
    """
    return self.deque[self.left] if self.deque[self.left] != None else -1
1
2
3
4
5
def getRear(self) -> int:
    """
    Get the last item from the deque.
    """
    return self.deque[self.right] if self.deque[self.right] != None else -1
1
2
3
4
5
6
7
8
9
10
11
def isEmpty(self) -> bool:
    """
    Checks whether the circular deque is empty or not.
    """
    return self.left == self.right+1

def isFull(self) -> bool:
    """
    Checks whether the circular deque is full or not.
    """
    return self.right - self.left == self.maxlength - 1