對(duì)于隊(duì)列的介紹在之前的文章一節(jié)寫(xiě)過(guò)了——http://www.reibang.com/p/41dc9265109a
這篇我是用的python內(nèi)置的列表，是使用適配器設(shè)計(jì)模式盹兢，實(shí)現(xiàn)了我們的隊(duì)列結(jié)構(gòu)。
缺點(diǎn)就是我們需要不斷地更新底層數(shù)組的大小授帕，這會(huì)讓某次操作的時(shí)間復(fù)雜度上升客给。雖然我們利用邊界攤銷(xiāo)，可以將平均下來(lái)的操作視為O(1)连锯。
今天我們用鏈表來(lái)實(shí)現(xiàn)隊(duì)列，讓每一個(gè)操作真正的達(dá)到O(1)用狱。
鏈表動(dòng)態(tài)的增刪运怖，代替了之前改變數(shù)組大小的操作，但是值得注意的是夏伊，鏈表在刪除尾結(jié)點(diǎn)的操作上摇展，并不高效，因?yàn)樗枰闅v鏈表拿到倒數(shù)第二個(gè)節(jié)點(diǎn)溺忧。
更通俗的說(shuō)法：如果只給定尾結(jié)點(diǎn)的引用 咏连，我們很難有效地刪除該節(jié)點(diǎn)盯孙。因?yàn)槲覀儧](méi)法拿到他的前驅(qū)節(jié)點(diǎn)的引用。
根據(jù)隊(duì)列先進(jìn)先出的特點(diǎn)祟滴，它只能在隊(duì)尾添加元素振惰，在隊(duì)頭刪除元素，所以我們把鏈表容易刪除的一端——鏈表頭作為隊(duì)頭垄懂，把鏈表尾作為隊(duì)尾骑晶，為了我們添加元素方便，我們還需要維護(hù)一個(gè)_tail引用來(lái)指向鏈表尾元素草慧，這樣我們?cè)谔砑右粋€(gè)新的元素的時(shí)候桶蛔，就不用遍歷鏈表來(lái)拿到尾結(jié)點(diǎn)的引用了。
這次的實(shí)現(xiàn)與昨大前天的實(shí)現(xiàn)椔龋——http://www.reibang.com/p/fe9c422db4de很像仔雷。
在實(shí)現(xiàn)的時(shí)候需要注意的一點(diǎn)是，當(dāng)執(zhí)行出隊(duì)列的操作舔示，而隊(duì)列中只有一個(gè)元素的時(shí)候碟婆，我們?cè)趯⒆詈笠粋€(gè)元素出隊(duì)列后，我們需要把_tail的引用改為None惕稻，因?yàn)榇藭r(shí)的tail是指向最后一個(gè)元素脑融，我們把頭節(jié)點(diǎn)后移后，尾結(jié)點(diǎn)的引用還是在的缩宜，這樣可以利于python進(jìn)行垃圾回收。
源代碼：
class Empty(Exception):
pass
class LinkedQueue:
class _Node:
def __init__(self, element, next):
self._element = element
self._next = next
def __init__(self):
self._head = None
self._tail = None
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def first(self):
if self.is_empty():
raise Empty("Queue is empty!")
return self._head._element
def enqueue(self, e):
newest = self._Node(e, None)
if self.is_empty():
self._head = newest
else:
self._tail._next = newest
self._tail = newest
self._size += 1
def dequeue(self):
if self.is_empty():
raise Empty("Queue is empty!")
answer = self._head
self._head = self._head._next
self._size -= 1
if self.is_empty():
self._tail = None
return answer
這次與上次一樣沒(méi)有實(shí)現(xiàn)str方法甥温，當(dāng)然遍歷鏈表也可以實(shí)現(xiàn)查看隊(duì)列的內(nèi)容锻煌，但是我覺(jué)得數(shù)據(jù)結(jié)構(gòu)應(yīng)該具有封裝性，用戶不應(yīng)該訪問(wèn)數(shù)據(jù)結(jié)構(gòu)的內(nèi)部情況姻蚓。
