Chương trình thiết kế một hàng đợi di chuyển phần tử được sử dụng gần đây nhất đến cuối phần tử đó bằng Python

Giả sử, chúng tôi được yêu cầu thiết kế một hàng đợi di chuyển phần tử được sử dụng gần đây nhất đến cuối nó. Hàng đợi sẽ được khởi tạo với các số nguyên từ 1 đến n. Bây giờ chúng ta phải xây dựng một hàm để bất cứ khi nào nó được gọi, nó sẽ di chuyển giá trị từ vị trí đã cho làm đầu vào của nó đến cuối hàng đợi. Chúng tôi sẽ gọi hàm nhiều lần và hàm sẽ trả về giá trị hiện tại ở cuối hàng đợi trong khi thực hiện tác vụ di chuyển của nó.

Vì vậy, nếu hàng đợi được khởi tạo với giá trị n =5 hoặc nó chứa các giá trị từ 1 đến 5.; và các vị trí nơi di chuyển được thực hiện lần lượt là 5, 2, 3 và 1, khi đó đầu ra sẽ là 5, 2, 4, 1

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

i:=vị trí trong chỉ mục mảng - 1, nơi giá trị k có thể được chèn vào bên phải để duy trì thứ tự đã sắp xếp
x:=delete (k - index [i]) phần tử khỏi dữ liệu [i]
đối với ii trong phạm vi i + 1 đến kích thước của chỉ mục, thực hiện
- index [ii]:=index [ii] - 1
nếu kích thước của phần tử cuối cùng của dữ liệu> =nn, thì
- chèn một danh sách mới vào cuối dữ liệu danh sách
- chèn n vào cuối chỉ mục danh sách
chèn x vào cuối dữ liệu
nếu dữ liệu [i] là rmpty, thì
- xóa phần tử thứ i khỏi dữ liệu
- xóa phần tử thứ i khỏi chỉ mục
trả về x

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

queue = TestQueue(5)
print(queue.solve(5))
print(queue.solve(2))
print(queue.solve(3))
print(queue.solve(1))

Đầu ra