Pythonで最後に使用された要素をその最後に移動するキューを設計するプログラム

最近使用した要素をその最後に移動するキューを設計するように求められたとします。キューは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
• データの最後の要素のサイズ>=nnの場合、
  • リストデータの最後に新しいリストを挿入します
  • リストインデックスの最後にnを挿入
• データの最後にxを挿入
• data [i]がrmptyの場合、
  • データからi番目の要素を削除する
  • インデックスからi番目の要素を削除する
• return 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