صف پیوندی اصلاح شده به چه معناست ؟

صف پیوندی اصلاح شده به چه معناست ؟

ما مایلیم یک پیادهسازي ADT صف بتواند همۀ عملیات را به صورت ثابـت-زمـانی انجـام دهـد. یک راه براي انجام این کار تغییر دادن کلاس صف بهطوري است که آدرسی به اولین و آخـرین گـره را  نگهداري کند. پیادهسازي صف اصلاحشده به این صورت است:

class ImprovedQueue:
def __init__(self):
self.length = 0
self.head = None
self.last = None
def isEmpty(self):
return (self.length == 0)

تاکنون تنها تغییر مشخصۀ last است که در متـدهاي remove و insert اسـتفاده شـده است:

class ImprovedQueue:
…
def insert(self, cargo):
node = Node(cargo)
node.next = None
if self.length == 0:
# if list is empty, the new node is head and last
self.head = self.last = node
else:
# find the last node
last = self.last
# append the new node
last.next = node
self.last = node
self.length = self.length + 1

از آنجا که last رد آخرین گره را نگه میدارد، مـا مجبـور نیسـتیم آن را جسـتجو کنـیم. در نتیجه این متد ثابت-زمانی است. براي بدست آوردن این سرعت باید هزینـهاي پرداخـت. مـا مجبـوریم براي متغیر last به None در زمانی که آخزین گره حذف شده است بـه remove حالـت خاصـی را اضافه کنیم:

class ImprovedQueue:
…
def remove(self):
cargo = self.head.cargo
self.head = self.head.next
self.length = self.length – 1
if self.length == 0:
self.last = None
return cargo

این پیادهسازي نسبت به پیادهسازي صف پیوندي پیچیـدهتـر و اثبـات آن هـم دشـوارتر اسـت. نتیجه این است که ما به هدفمان دست یافتیم؛ هر دو متد insert و remove عملیات ثابت زمـانی هستند.

تمرین 19-1 :یک پیادهسازي از ADT صف را با استفاده از لیستهاي پایتون بنویسـید. کـارائی این پیاده سازي را با کلاس ImprovedQueue براي محدودهاي از طولهـاي صـف مقایسـه کنید.

برای اموزش های ویدیویی زبان پایتون به بستر ویدیو های اموزشی بروید

بستر اموزش های ویدویی