Циклические очереди

Две реализации очереди

Начнём с решения задания 1 из прошлого листка.

def make_queue(cap): return ([None]*cap,0,0)  

def queue_size(q):
    a,b,c = q
    return (c-b) % len(a)

def queue_is_full(q):
    return queue_size(q)+1 == len(q[0])

def queue_push(q,x):
    a,b,c = q
    a[c] = x
    c = (c+1) % len(a)
    return (a,b,c)

def queue_pop(q):
    a,b,c = q
    taken = a[b]
    b = (b+1) % len(a)
    return taken, (a,b,c)

В этой реализации функция queue_pop возвращает вместе с забранным элементом новую тройку массив-начало-конец (имеющую со старой только общий массив). Добавление или удаление элемента в такую очередь происходит при помощи конструкций

q = queue_push(q, foo)
q,foo = queue_pop(q)

Недостатком такого представления очереди является смесь мутабельных (изменяемых) и иммутабельных (неизменяемых) типов данных. Более естественно (с точки зрения языка python) следующее представление:

def make_queue(cap): return [[None]*cap,0,0]

def queue_push(q,x):
    a,b,c = q
    a[c] = x
    q[2] = (c+1) % len(a)

def queue_pop(q):
    a,b,c = q
    taken = a[b]
    q[1] = (b+1) % len(a)
    return taken

Здесь добавление и удаление элемента происходит весьма стандартно:

queue_push(q,foo)
foo = queue_pop(q)

Задание

  1. В терминах очереди первого типа реализуйте make_front, take_from, extend, is_empty так, чтобы нижеприведённая функция совершала обход графа в ширину.
def traverse(graph, is_good, start):
    front   = make_front([start])
    visited = set()
    while not is_empty(front):
        vertex = take_from(front)
        if vertex in visited: continue
        visited.add(vertex)
        if is_good(vertex): return vertex

        to_visit = [n for n in neighbors(graph,vertex)
                      if  n not in visited]

        extend(front,to_visit)

  1. Сделайте то же самое в терминах очереди второго типа.

  2. В терминах induct из предыдущего листка определите функцию iterate(f,n,x), для которой

iterate(f,n,x) = f(f(f(...f(x))))  # f применено n раз

При решении третьей задачи запрещается явно или неявно использовать встроенные в python числовые типы (int и float). Аргумент n здесь — натуральное число в смысле раздела про абстрактные типы данных.