पायथन में सबसे हाल ही में उपयोग किए गए एलिमेंट को अंत में ले जाने वाली क्यू डिजाइन करने का प्रोग्राम

मान लीजिए हमें एक क्यू डिजाइन करने के लिए कहा गया है जो सबसे हाल ही में उपयोग किए गए एलिमेंट को अंत में ले जाती है। क्यू को 1 से n तक के इंटीजर नंबर्स से इनिशियलाइज़ किया जाएगा। अब हमें एक फ़ंक्शन बनाना है ताकि जब भी इसे कॉल किया जाए, यह इनपुट के रूप में दी गई पोजीशन से मान को क्यू के अंत में ले जाए। हम फ़ंक्शन को कई बार कॉल करेंगे, और फ़ंक्शन क्यू के अंत में वर्तमान में मौजूद मान को वापस करेगा जबकि अपना मूविंग टास्क करता है।

उदाहरण के लिए, यदि क्यू को n = 5 मान से इनिशियलाइज़ किया गया है, या इसमें 1 से 5 तक के मान हैं; और जिन पोजीशन पर मूव किया जाता है वे क्रमशः 5, 2, 3, और 1 हैं, तो आउटपुट 5, 2, 4, 1 होगा।

हल करने के चरण

1. i := ऐरे इंडेक्स में पोजीशन - 1, जहां मान k को सॉर्टेड ऑर्डर बनाए रखते हुए दाईं ओर डाला जा सकता है।
2. x := data[i] से (k - index[i])-वां एलिमेंट हटाएं।
3. ii को i+1 से index के आकार तक लूप चलाएं:
   • index[ii] := index[ii] - 1
4. यदि data के अंतिम एलिमेंट का आकार >= nn, तो:
   • data के अंत में एक नई सूची डालें
   • n को index सूची के अंत में डालें
5. x को data के अंत में डालें।
6. यदि data[i] खाली है, तो:
   • data से i-वां एलिमेंट हटाएं
   • index से i-वां एलिमेंट हटाएं
7. 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