在 python 中实现一个支持撤消功能的队列

Question

我被要求在python中创建一个具有以下3个命令的队列：

• 排队
• 流行
• 撤消

撤消命令将撤消上一个排队或弹出命令。

这是我写的： 它需要命令的数量，然后是命令本身。 我使用第二个队列来存储第一个队列的先前状态。

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

这里的重要问题，如果您需要"可撤消撤消"？

无论如何，我强烈建议将逻辑封装到单个类中，因为在操作松散对象时很容易迷失逻辑。

让我们假设您不需要撤消 undo，有点粗略的实现：

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 个任务的 deque，1 个大小限制(或无大小(的 deque，不断跟踪如何"撤消"操作。普通任务 deque 用作 FIFO 队列 — 因此您在一侧追加，从另一侧弹出。撤消 deque 用作 LIFO/堆栈 — 最后一个上下文是用于撤消操作的上下文。

棘手的是，正常队列和 unto 队列在每个操作以及参数中都会被反转。即您需要为弹出撤消保留上下文。