## Remarks

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

### Implementation

• An implementation of Queue using linked list.
class Node:
def __init__(self, item=None):
self.item = item
self.next = None

class Queue:
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):

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