设计一个队列的程序,在 Python 中将最近使用的元素移动到它的末尾
假设,我们被要求设计一个队列,将最近使用的元素移动到它的末尾。队列将被初始化为整数1到n。现在我们必须构建一个函数,以便无论何时调用它,它都会将值从作为其输入给出的位置移动到队列的末尾。我们将多次调用该函数,该函数将在执行其移动任务时返回当前位于队列末尾的值。
因此,如果队列使用值n=5进行初始化,或者它包含从1到5的值。并且执行移动的位置分别为5,2,3,1,那么输出将是5,2,4,1
示例
让我们看看以下实现以获得更好的理解-
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