สมมติว่า เราถูกขอให้ออกแบบคิวที่ย้ายองค์ประกอบที่ใช้ล่าสุดไปยังจุดสิ้นสุด คิวจะเริ่มต้นด้วยเลขจำนวนเต็ม 1 ถึง n ตอนนี้ เราต้องสร้างฟังก์ชันเพื่อให้เมื่อใดก็ตามที่ถูกเรียก มันจะย้ายค่าจากตำแหน่งที่กำหนดเป็นอินพุตไปยังจุดสิ้นสุดของคิว เราจะเรียกใช้ฟังก์ชันหลายครั้ง และฟังก์ชันจะคืนค่าปัจจุบันที่ส่วนท้ายของคิวขณะดำเนินการเคลื่อนย้าย
ดังนั้น หากคิวเริ่มต้นด้วยค่า n =5 หรือมีค่าตั้งแต่ 1 ถึง 5 และตำแหน่งที่ทำการเคลื่อนไหวคือ 5, 2, 3 และ 1 ตามลำดับ จากนั้นผลลัพธ์จะเป็น 5, 2, 4, 1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- i :=ตำแหน่งในดัชนีอาร์เรย์ - 1 โดยที่ค่า k สามารถแทรกทางด้านขวาเพื่อรักษาลำดับที่จัดเรียงไว้ได้
- x :=ลบ (k - index[i])th องค์ประกอบจาก data[i]
- สำหรับ ii ในช่วง i+1 ถึงขนาดของดัชนี ทำ
- ดัชนี[ii] :=ดัชนี[ii] - 1
- ถ้าขนาดขององค์ประกอบสุดท้ายของ data>=nn แล้ว
- แทรกรายการใหม่ที่ส่วนท้ายของข้อมูลรายการ
- แทรก n ที่ส่วนท้ายของดัชนีรายการ
- แทรก x ที่ส่วนท้ายของข้อมูล
- ถ้า data[i] เป็น rmpty แล้ว
- ลบองค์ประกอบ ith ออกจากข้อมูล
- ลบองค์ประกอบ ith ออกจากดัชนี
- ผลตอบแทน 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
