用 Python 编写一个程序，设计一个将最近使用的元素移动到队列末尾的队列
pythonserver side programmingprogramming更新于 2025/12/9 20:28:17
假设，我们被要求设计一个将最近使用的元素移动到队列末尾的队列。该队列将用 1 到 n 的整数初始化。现在我们必须构建一个函数，以便每次调用它时，它都会将值从输入的位置移动到队列末尾。我们将多次调用该函数，该函数将在执行移动任务时返回当前位于队列末尾的值。
因此，如果队列用值 n = 5 初始化，或者它包含从 1 到 5 的值。；并且执行移动的位置分别为 5、2、3 和 1，则输出将为 5、2、4、1
为了解决这个问题，我们将遵循以下步骤 −
- i := 数组索引 - 1 中的位置，其中值 k 可以插入到保持排序顺序的右侧
- x := 从 data[i] 中删除 (k - index[i]) 个元素
- 对于 i+1 到索引大小范围内的 ii，执行
- index[ii] := index[ii] - 1
- 如果 data 的最后一个元素的大小>= nn，则
- 在列表 data 的末尾插入一个新列表
- 在列表末尾插入 n索引
- 在数据末尾插入 x
- 如果 data[i] 为 rmpty，则
- 从数据中删除第 i 个元素
- 从索引中删除第 i 个元素
- 返回 x
示例
让我们看看下面的实现以便更好地理解 −
from bisect import bisect_right from math import sqrt class TestQueue: def __init__(self, n): self.n = n self.nn = int(sqrt(n)) self.data = [] self.index = [] for i in range(1, n+1): ii = (i-1)//self.nn if ii == len(self.data): self.data.append([]) self.index.append(i) self.data[-1].append(i) def solve(self, k): i = bisect_right(self.index, k)-1 x = self.data[i].pop(k - self.index[i]) for ii in range(i+1, len(self.index)): self.index[ii] -= 1 if len(self.data[-1]) >= self.nn: self.data.append([]) self.index.append(self.n) self.data[-1].append(x) if not self.data[i]: self.data.pop(i) self.index.pop(i) return x queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))
输入
queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))
输出
5 2 4 1
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
