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