<big>編譯環(huán)境：python v3.5.0, mac osx 10.11.4</big>
什么是隊(duì)列
- 具有一定操作約束的線性表，只能在一端插入，在另一端刪除。
- 數(shù)據(jù)插入（入隊(duì)列，AddQ），數(shù)據(jù)刪除（DeleteQ）
-
先入先出（FIFO）
如同生活中的排隊(duì)買票，排在隊(duì)頭的先買票，排在隊(duì)尾的最后一個(gè)最后才能買票。
隊(duì)列的抽象數(shù)據(jù)類型描述
隊(duì)列的順序存儲(chǔ)（數(shù)組）實(shí)現(xiàn)
- 基礎(chǔ)實(shí)現(xiàn)：由一個(gè)數(shù)組和兩個(gè)指針構(gòu)成，插入元素則是指向后的指針（rear）后移一位，刪除元素則把指向前的元素（front）后移一位，當(dāng)隊(duì)列為空時(shí)兩個(gè)指針指向同一個(gè)位置。(queue.py)
# -- coding: utf-8 --
class Queue():
def init(self, maxSize): # 初始化隊(duì)列,頭和尾都指向-1
self._front = -1
self._rear = -1
self._q = [None] * maxSize
def addElem(self, element):
if self._rear == len(self._q)-1: # 如果rear指向了隊(duì)列的最后一個(gè)元素,則隊(duì)列滿了
print('it is a full queue!')
else:
self._rear += 1
self._q[self._rear] = element
print('add ' + str(element) + ' in Queue')
def deleteElem(self): # 刪除front指向的元素,并放回被刪除的元素
if self._front == self._rear: # 如果front 和 rear指向同一個(gè)元素,則隊(duì)列為空
print('it is an empty queue!')
else:
self._front += 1
value = self._q[self._front]
print('add ' + str(value) + ' in Queue')
self._q[self._front] = None # 刪除元素
return value - 順環(huán)隊(duì)列：顯然當(dāng)上述隊(duì)列的實(shí)現(xiàn)不能充分的利用存儲(chǔ)空間，即當(dāng)每個(gè)存儲(chǔ)單元只能存儲(chǔ)一次元素，當(dāng)進(jìn)行delete操作后，就一直空著了。這并不是我們想要的結(jié)果，所以為了高效的利用計(jì)算機(jī)存儲(chǔ)空間，我們一般利用順環(huán)隊(duì)列進(jìn)行實(shí)現(xiàn)。
實(shí)現(xiàn)關(guān)鍵：對(duì)front和rear都采用<big>“加一取余”</big>的辦法來(lái)實(shí)現(xiàn)順序存儲(chǔ)的循環(huán)利用，且rear和front起始都指向位置0而不是1。(queue.py)
# -- coding: utf-8 --
class Queue():
def init(self, maxSize): # 初始化隊(duì)列,頭和尾都指向0
self._front = 0
self._rear = 0
self._q = [None] * maxSize
def addElem(self, element):
if (self._rear + 1) % len(self._q) == self._front: # 對(duì)rear進(jìn)行加一取余數(shù)(實(shí)現(xiàn)循環(huán)利用),但到達(dá)最大數(shù)時(shí)歸到起始位置即0,1,2,3,4,0,1,2,3,4依次循環(huán)
print('it is a full queue!')
else:
self._q[self._rear] = element
self._rear = (self._rear + 1) % len(self._q)
#print(str(self._rear)+'----'+str(self._front))
print('add ' + str(element) + ' in Queue')
def deleteElem(self): # 刪除front指向的元素,并放回被刪除的元素
if self._front == self._rear: # 如果front 和 rear指向同一個(gè)元素,則隊(duì)列為空
print('it is an empty queue!')
else:
value = self._q[self._front]
self._q[self._front] = None # 刪除元素
self._front = (self._front + 1) % len(self._q) # 對(duì)rear進(jìn)行加一取余數(shù)(實(shí)現(xiàn)循環(huán)利用),但到達(dá)最大數(shù)時(shí)歸到起始位置
print('delete ' + str(value) + ' out of Queue')return value
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)（鏈表）實(shí)現(xiàn)
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也可以由單向鏈表實(shí)現(xiàn)。由于刪除操作作用在front頭，所以front指向頭節(jié)點(diǎn)。(queue_chain.py)
class Note():
def __init__(self,value=None,next=None):
self.value = value
self.next = next
class queueChain:
def __init__(self,front=None,rear=None):
self.front = front # fron指向表頭的指針
self.rear = rear # rear指向表尾的指針
def inQue(queue, value): # 入隊(duì)操作
newNote = Note(value)
if queue.front is None: # 鏈表為空,將front 賦值給表頭
queue.front = queue.rear = newNote
else:
queue.rear.next = newNote
queue.rear = newNote
print('add '+str(value)+' in the queue' )
def outQue(queue): # 出隊(duì)操作
if queue.front is None : # 如果front指向?yàn)榭?則鏈表為空
print('it is an empty queue!')
else:
p = queue.front
element = p.value
if queue.front == queue.rear: # 如果前后指針指向一個(gè)元素,則全部重置為None
queue.front = queue.rear = None
else:
queue.front = p.next
del p # 釋放空間
print('delete ' + str(element) +' out of Queue')
return element
