1  
  2  class Deque:
  3      """
  4      A Deque: a double-ended queue (combined stack and queue data structure)
  5      """
  6  
  7      def __init__(self):
  8          self.array = [None for _ in range(4)]   # underlying array
  9          self.capacity = 4   # the capacity of the underlying array
 10          self.size = 0       # the number of elements stored
 11          self.head = 0       # the head index (guaranteed to be valid index)
 12          self.tail = 0       # the tail index at which to insert (guaranteed to be valid index)
 13  
 14  
 15      def push(self, x):
 16          # Double capacity if needed
 17          if self.capacity == self.size:
 18              self.copy_into([None for _ in range(self.capacity * 2)])
 19  
 20          # Put element at tail of array
 21          self.array[self.tail] = x
 22          self.tail = (self.tail + 1) % self.capacity
 23          self.size += 1
 24  
 25  
 26      def pop(self):
 27          return self.remove(head=False)
 28  
 29  
 30      def enqueue(self, x):
 31          self.push(x)
 32  
 33  
 34      def dequeue(self):
 35          return self.remove(head=True)
 36  
 37  
 38      def remove(self, head):
 39          """
 40          Removes and returns element from head/tail. Downsizes array if small enough
 41          :param head: If true, removes from head, else from tail
 42          """
 43          if self.size == 0:
 44              raise Exception('Deque is empty')
 45          self.size -= 1
 46  
 47          # Wipe and store the removed element
 48          if head:
 49              ret = self.array[self.head]
 50              self.array[self.head] = None
 51              self.head = (self.head + 1) % self.capacity
 52          else:
 53              ret_idx = (self.tail - 1) % self.capacity
 54              ret = self.array[ret_idx]
 55              self.array[ret_idx] = None
 56              self.tail = ret_idx
 57  
 58          # Downsize array if needed (minimum capacity 4)
 59          if self.capacity > 4 and self.size <= self.capacity / 4:
 60              self.copy_into([None for _ in range(self.capacity // 2)])
 61  
 62          return ret
 63  
 64  
 65      def copy_into(self, new_array):
 66          """
 67          Copies elements from self.array into new_array and updates internal state
 68          """
 69          for i in range(self.size):
 70              new_array[i] = self.array[(i + self.head) % self.capacity]
 71          self.capacity = len(new_array)
 72          self.array = new_array
 73          self.head, self.tail = 0, self.size
 74  
 75  
 76  
 77  "========= Testing Deque ========="
 78  
 79  def test_deque():
 80      d = Deque()
 81      print(d.array)
 82  
 83      d.push(1)
 84      d.push(2)
 85  
 86      print(d.array)
 87  
 88      print(d.dequeue())
 89      print(d.array)
 90  
 91      d.enqueue(3)
 92      d.enqueue(4)
 93      print(d.array)
 94      d.enqueue(5)
 95      print(d.array)
 96      d.enqueue(6)
 97      print(d.array)
 98  
 99      print(d.pop())
100      print(d.dequeue())
101      print(d.array)
102  
103  
104      for i in range(6, 20):
105          d.push(i)
106      print(d.array)