Как отменить простую очередь (FIFO), используя еще одну простую очередь (FIFO)? - PullRequest
Новая
       16

Как отменить простую очередь (FIFO), используя еще одну простую очередь (FIFO)?

0 голосов
/ 31 января 2019

Давайте возьмем первую очередь, которая содержит элементы 1,2,3,4 по порядку, поэтому первая очередь становится 1,2,3,4, фронт равен 1, а сзади равен 4. У нас есть еще одна пустая очередь, содержащая ноль элементов.,Как мы можем повернуть эту первую очередь, используя другую очередь, которая пуста?(Мы не можем использовать третью очередь для реверса.)

Я пытался реверсировать очередь, используя еще одну очередь, но у меня в голове не было решения.

Так что я ожидаю, что очередь будет перевернута так,что первые элементы очереди становятся 4,3,2,1 после реверса.

1 Ответ

0 голосов
/ 01 февраля 2019 
from tqdm import tqdm

def rotate(q, k):
    move(q, q, k)

def move(q1, q2, k):
    for i in range(k):
        q2.append(q1.pop(0))


def reverse(q1):
    q2 = []
    for i in range(1, len(q1)):
        move(q1, q2, len(q1) - i)
        rotate(q2, len(q2) - 1)
        move(q2, q1, len(q2))
        rotate(q1, i + 1)

    return q1


if __name__ == '__main__':

    for i in tqdm(range(1000)):
        rq =  reverse(range(i))
        assert rq == range(i)[::-1]
...