设计Python中将最近使用的元素移到队列末尾的程序

设计Python中将最近使用的元素移到队列末尾的程序

假设我们被要求设计一个队列,它可以将最近使用的元素移动到队列的末尾。队列将用1到n的整数数字初始化。现在我们必须建立一个函数,每当被调用时,它就会将从其输入给定的位置移动的值移动到队列的末尾。我们将多次调用该函数,而函数将在执行移动任务时返回当前位于队列末尾的值。

因此,如果队列用值n = 5初始化或包含从1到5的值,并且所执行的移动位置分别是5、2、3和1,则输出将为5、2、4、1.

为了解决这个问题,我们将遵循以下步骤:

  • i:在数组索引中的位置,插入值k以维持排序顺序的右边
  • x:从data[i]中删除(k – index[i])元素
  • 对于i + 1到index大小的范围内的ii,执行以下操作:
    • index [ii]:= index[ii] – 1
  • 如果data的最后一个元素的大小> = nn,则
    • 在list data的末尾插入一个新的列表
    • 在list index的末尾插入n
  • 将x插入data的末尾
  • 如果data [i]为空,则
    • 从data中删除第i个元素
    • 从index中删除第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教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程