# Implementation of the Queue ADT using a linked list
class LinkedListQueue:

	# Creates an empty queue.
	def __init__(self):
		self._qhead = None
		self._qtail = None
		self._count = 0

	# Returns True if the queue is empty.
	def isEmpty(self):
		return self._qhead is None

	# Returns the number of items in the queue.
	def __len__(self):
		return self._count

	# Adds the given item to the queue.
	def enqueue(self, item):
		node = _QueueNode( item )
		if self.isEmpty():
			self._qhead = node
		else:
			self._qtail.next = node

		self._qtail = node
		self._count += 1

	# Removes and return the first item in the queue.
	def dequeue(self):
		assert not self.isEmpty(), "Cannot dequeue from an empty queue."
		node = self._qhead
		if self._qhead is self._qtail:
			self._qtail = None
			self._qhead = self._qhead.next
			self._count -= 1
			return node.item

	# Private storage class for creating the linked list nodes.
	class _QueueNode(object):
		def __init__(self, item):
			self.item = item
			self.next = None

from array import Array

# Implementation of the Queue ADT using a circular array.
class CircularArrayQueue:

	# Creats an empty queue
	def __init__(self, maxSize):
		self._count = 0
		self._font = 0
		self._back = maxSize - 1
		self._qArray = Array( maxSize )

	# Returns True if the queue is empty.
	def isEmpty(self):
		return self._count == 0

	# Returns True if the queue is full.
	def isFull(self):
		return self._count == len( self._qArray )

	# Returns the number of items in the queue.
	def __len__(self):
		return self._count

	# Adds the given item to the queue.
	def enqueue(self, item):
		assert not self.isFull(), "Cannot enqueue to a full queue."
		maxSize = len( self._qArray )
		self._back = ( self._back + 1 ) % maxSize
		self._qArray[self._back] = item
		self._count += 1

	# Removes and returns the first item in the queue.
	def dequeue(self):
		assert not self.isEmpty(), "Cannot dequeue from an empty queue."
		item = self._qArray[self._font]
		maxSize = len( self._qArray )
		self._font = ( self._font + 1 ) % maxSize
		self._count -= 1
		return item





	
