Source code for tryalgo.our_queue
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
A FIFO queue
christoph dürr - jill-jênn vie - 2015-2019
"""
# snip{ OurQueue
# pylint: disable=missing-docstring
[docs]
class OurQueue:
"""A FIFO queue
Complexity:
all operators in amortized constant time,
except __str__ which is linear
"""
def __init__(self):
self.in_stack = [] # tail
self.out_stack = [] # head
def __len__(self):
return len(self.in_stack) + len(self.out_stack)
[docs]
def push(self, obj):
self.in_stack.append(obj)
[docs]
def pop(self):
if not self.out_stack: # head is empty
# Note that the in_stack is assigned to the out_stack
# in reverse order. This is because the in_stack stores
# elements from oldest to newest whereas the out_stack
# needs to pop elements from newest to oldest
self.out_stack = self.in_stack[::-1]
self.in_stack = []
return self.out_stack.pop()
# snip}
def __str__(self):
return str(self.out_stack[::-1] + self.in_stack)