Write the Python method add(a, b) for the class BigInteger, where a and b are queues that represent integer numbers. Each node in such a queue contains a single digit. The digits are stored in reverse order, with the 1's digit at the head of the queue. add(a, b) should return the number that is the sum of the linked-list numbers a and b.

For example, 617 + 295 = 912 would be represented in the linked-list implementation of a queue as (7->1->6) + (5->9->2) = (2->1->9)

biginteger.py

from linkedlistqueue import LinkedListQueue class BigInteger: @staticmethod def add(a, b): """Add two integers represented as LinkedListQueues, least-significant-digit first""" result = LinkedListQueue() # TODO Add code here return result def simpleTest(): # You do not have to include this method in your submission, but it or # methods like it will help you while debugging your code. # For example, here's the code to replicate the example: a = LinkedListQueue() # will hold 6 1 7 a.enqueue(7) a.enqueue(1) a.enqueue(6) b = LinkedListQueue() # will hold 2 9 5 b.enqueue(5) b.enqueue(9) b.enqueue(2) c = BigInteger.add(a, b) # should now hold 9 1 2 print(c.dequeue()) # should print 2 print(c.dequeue()) # should print 1 print(c.dequeue()) # should print 9 print(len(c)) # should print 0 (nothing left in list)

linkedlistqueue.py

class LinkedListQueue: """FIFO queue implementation using a singly linked list for storage.""" # -------------------------- nested _Node class -------------------------- class _Node: """Lightweight, nonpublic class for storing a singly linked node.""" __slots__ = '_element', '_next' # streamline memory usage def __init__(self, element, next): self._element = element self._next = next # ------------------------------- queue methods -------------------------- def __init__(self): """Create an empty queue.""" self._head = None self._tail = None self._size = 0 # number of queue elements def __len__(self): """Return the number of elements in the queue.""" return self._size def is_empty(self): """Return True if the queue is empty.""" return self._size == 0 def first(self): """Return (but do not remove) the element at the front of the queue.""" if self.is_empty(): raise Exception('Queue is empty') return self._head._element # front aligned with head of list def dequeue(self): """Remove and return the first element of the queue (i.e., FIFO).""" if self.is_empty(): raise Exception('Queue is empty') answer = self._head._element self._head = self._head._next self._size -= 1 if self.is_empty(): # special case as queue is empty self._tail = None # removed head had been the tail return answer def enqueue(self, e): """Add an element to the back of queue.""" newest = self._Node(e, None) # node will be new tail node if self.is_empty(): self._head = newest # special case as previously empty else: self._tail._next = newest self._tail = newest # update reference to tail node self._size += 1