queue_by_two_stacks.py

"""Queue implementation using two stacks"""

fromcollections.abcimportIterable
fromtypingimportGeneric, TypeVar

_T=TypeVar("_T")


classQueueByTwoStacks(Generic[_T]):
def__init__(self, iterable: Iterable[_T] |None=None) ->None:
"""
 >>> QueueByTwoStacks()
 Queue(())
 >>> QueueByTwoStacks([10, 20, 30])
 Queue((10, 20, 30))
 >>> QueueByTwoStacks((i**2 for i in range(1, 4)))
 Queue((1, 4, 9))
 """
self._stack1: list[_T] =list(iterableor [])
self._stack2: list[_T] = []

def__len__(self) ->int:
"""
 >>> len(QueueByTwoStacks())
 0
 >>> from string import ascii_lowercase
 >>> len(QueueByTwoStacks(ascii_lowercase))
 26
 >>> queue = QueueByTwoStacks()
 >>> for i in range(1, 11):
 ... queue.put(i)
 ...
 >>> len(queue)
 10
 >>> for i in range(2):
 ... queue.get()
 1
 2
 >>> len(queue)
 8
 """

returnlen(self._stack1) +len(self._stack2)

def__repr__(self) ->str:
"""
 >>> queue = QueueByTwoStacks()
 >>> queue
 Queue(())
 >>> str(queue)
 'Queue(())'
 >>> queue.put(10)
 >>> queue
 Queue((10,))
 >>> queue.put(20)
 >>> queue.put(30)
 >>> queue
 Queue((10, 20, 30))
 """
returnf"Queue({tuple(self._stack2[::-1] +self._stack1)})"

defput(self, item: _T) ->None:
"""
 Put `item` into the Queue

 >>> queue = QueueByTwoStacks()
 >>> queue.put(10)
 >>> queue.put(20)
 >>> len(queue)
 2
 >>> queue
 Queue((10, 20))
 """

self._stack1.append(item)

defget(self) ->_T:
"""
 Get `item` from the Queue

 >>> queue = QueueByTwoStacks((10, 20, 30))
 >>> queue.get()
 10
 >>> queue.put(40)
 >>> queue.get()
 20
 >>> queue.get()
 30
 >>> len(queue)
 1
 >>> queue.get()
 40
 >>> queue.get()
 Traceback (most recent call last):
 ...
 IndexError: Queue is empty
 """

# To reduce number of attribute look-ups in `while` loop.
stack1_pop=self._stack1.pop
stack2_append=self._stack2.append

ifnotself._stack2:
whileself._stack1:
stack2_append(stack1_pop())

ifnotself._stack2:
raiseIndexError("Queue is empty")
returnself._stack2.pop()


if__name__=="__main__":
fromdoctestimporttestmod

testmod()