Remarks

  • A queue is a abstract data type that is First-In-First-Out(FIFO).

Implementation

An implementation of Queue using linked list.

class Queue(object):
    class Node(object):
        def __init__(self, item=None):
            self.item = item
            self.next = None

    def __init__(self):
        self.first = None
        self.last = None
        self._n = 0

    @property
    def is_empty(self):
        return not self.first

    def __len__(self):
        return self.n

    def peek(self):
        return self.head.item

    def enqueue(self, item):
        prev = self.last
        self.last = self.Node(item)
        if self.is_empty():
            self.first = self.last
        else:
            prev.next = self.last
        self._n += 1

    def dequeue(self):
        assert not self.is_empty(), "Queue is empty"
        item = self.first.item
        self.first = self.first.next
        self._n -= 1
        if self.is_empty():
            self.last = None
        return item

An implementation of Queue using fixed length array and pointer.
Note the formula for pointer updates:

  • Enqueue: (first + n) % capacity
  • Dequeue: (first + 1) % capacity
    class Queue:
      def __init__(self, size):
          self.size = size
          self.queue = [None] * size
          self.first = 0
          self.n = 0
    
      def enqueue(self, item):
          assert not self.is_full(), 'Queue is full'
          self.queue[(self.first + self.n) % self.size] = value
          self.n += 1
    
      def dequeue(self):
          assert not self.is_empty(), 'Queue is empty'
          item = self.queue[self.first]
          self.queue[self.first] = None
          self.first = (self.first + 1) % self.size
          self.n -= 1
          return item
    
      def peek(self):
          return self.queue[self.first]
    
      def is_empty(self):
          return self.n == 0
    
      def is_full(self):
          return self.n == self.size
    

Sample Questions

Monotonic Queue