Реализовать очередь в Python, которая поддерживает функцию отмены

Question

Меня попросили создать в python очередь, в которой есть 3 команды:

• enqueue
• pop
• undo

Команда отмены отменит предыдущую команду enqueue или pop.

Вот что я написал: для этого нужно количество команд, а затем сами команды.Я использовал вторую очередь для хранения предыдущего состояния первой очереди.

from collections import deque

queue_1 = deque()
queue_2 = deque()
num_of_commands = int(input())
commands = []
for i in range(num_of_commands):
    commands.append(input())

for i in range(len(commands)):
    queue_2 = queue_1.copy()
    if 'enqueue' in commands[i]:
        queue_1.append(int((commands[i].split())[1]))
    elif 'pop' in commands[i]:
        if len(queue_1) != 0:
            print(queue_1.popleft())
    if i < len(commands) - 1:
        if ((commands[i + 1].split())[0]) == 'undo':
            queue_1 = queue_2.copy()

Пример ввода:

10
enqueue 1
enqueue 2
pop
undo
pop
enqueue 3
undo
pop
enqueue 10
pop

Пример вывода:

1
1
2
10

Но мойПроблема в том, что это не поддерживает последовательные команды отмены.Как я могу изменить его для поддержки нескольких последовательных команд отмены?

Answer 1

Важный вопрос здесь, если вам нужно «отменить отмену»?)

В любом случае, я настоятельно рекомендую инкапсулировать логику в один класс, легко потеряться с логикой, когда вы манипулируете свободными объектами.

Допустим, вам не нужно отменятьотмена, немного схематичная реализация:

class QueueWithUndo:
    def __init__(self, history=10):
        self.q = deque()
        self.undo_q = deque(maxlen=history)

    def enqueue(self, task):
        self.undo_q.append((self.q.pop, ))
        self.q.append(task)

    def pop(self):
        result = self.q.popleft()
        self.undo_q.append((self.q.append, result))
        return result

    def undo(self):
        op, *task = self.undo_q.pop()
        op(*task)

Идея проста - 1 дек для задач, 1 дек с ограниченным размером (или нет), который отслеживает, как "отменить" операции.Обычная очередь задач используется в качестве очереди FIFO - поэтому вы добавляете с одной стороны, а с противоположной.Отмена отмены используется в качестве LIFO / стека - последний контекст - это то, что используется для отмены вещей.

Хитрость заключается в том, что обычные и очереди превращаются в каждую операцию, также в качестве аргументов.Т.е. вам нужно сохранить контекст для pop отмены.