一、隊(duì)列概念

1、隊(duì)列是只有一端可以進(jìn)行插入操作，而另一端可以進(jìn)行刪除操作的有序線性存儲(chǔ)結(jié)構(gòu)，滿足先進(jìn)先出的約束。

2、在計(jì)算機(jī)科學(xué)中，隊(duì)列是一個(gè)集合，其中集合中的實(shí)體按順序保存，集合上的主要（或唯一）操作是向后端位置添加實(shí)體，稱為入隊(duì)，前端位置并刪除實(shí)體，稱為出隊(duì)。這使得隊(duì)列成為先進(jìn)先出（FIFO）數(shù)據(jù)結(jié)構(gòu)。在FIFO數(shù)據(jù)結(jié)構(gòu)中，添加到隊(duì)列的第一個(gè)元素將是第一個(gè)要?jiǎng)h除的元素。這相當(dāng)于一旦添加新元素，在刪除新元素之前必須刪除之前添加的所有元素的要求。通常偷看或還輸入了前面的操作，返回前面元素的值而不使其出列。隊(duì)列是線性數(shù)據(jù)結(jié)構(gòu)的示例，或者更抽象地是順序集合。

3、隊(duì)列提供計(jì)算機(jī)科學(xué)，運(yùn)輸和運(yùn)營研究中的服務(wù)，其中存儲(chǔ)和保存諸如數(shù)據(jù)，對(duì)象，人或事件的各種實(shí)體以便稍后處理。在這些上下文中，隊(duì)列執(zhí)行緩沖區(qū)的功能。隊(duì)列在計(jì)算機(jī)程序中很常見，它們被實(shí)現(xiàn)為與訪問例程耦合的數(shù)據(jù)結(jié)構(gòu)，作為抽象數(shù)據(jù)結(jié)構(gòu)或作為類的面向?qū)ο笳Z言。常見的實(shí)現(xiàn)是循環(huán)緩沖區(qū)和鏈表。

• 生活中典型的實(shí)例就是排隊(duì)，先到的人排在前面，可先得到服務(wù)，后到的人排在后面，并且不能插隊(duì)。
• 計(jì)算機(jī)應(yīng)用中典型的實(shí)例就是打印機(jī)，先發(fā)送的打印任務(wù)可以先被執(zhí)行，之后的都要排隊(duì)等候

二、Python實(shí)現(xiàn)

1、在 Python 中，和棧一樣，同樣可以用列表作為隊(duì)列的底層實(shí)現(xiàn)，只需要確定列表的哪一端作為隊(duì)列的頭，也即刪除操作端（先進(jìn)先出），哪一端作為隊(duì)列的尾，也即插入操作端（后進(jìn)后出）。同時(shí)，把隊(duì)列抽象為類，隊(duì)列的先進(jìn)先出操作實(shí)現(xiàn)為類的方法。

2、從理論上講，隊(duì)列的一個(gè)特征是它沒有特定的容量。無論已包含多少元素，始終可以添加新元素。它也可以是空的，此時(shí)在再次添加新元素之前刪除元素是不可能的。

3、隊(duì)列的Python實(shí)現(xiàn)：

Queue.qsize() 返回隊(duì)列的大小

Queue.empty() 如果隊(duì)列為空，返回True,反之False

Queue.full() 如果隊(duì)列滿了，返回True,反之False，Queue.full 與 maxsize 大小對(duì)應(yīng)

Queue.get()從隊(duì)列中移除并返回?cái)?shù)據(jù)

Queue.get_nowait() 相當(dāng)于Queue.get(False)，非阻塞方法

Queue.put(item[, block[, timeout]])
將item放入隊(duì)列

• timeout為正整數(shù)時(shí)，等待超時(shí)則拋出Full異常

• block為False時(shí)，有空間可將數(shù)據(jù)放入隊(duì)列，立即拋出Full異常

Queue.task_done() 在完成一項(xiàng)工作之后，Queue.task_done()函數(shù)向任務(wù)已經(jīng)完成的隊(duì)列發(fā)送一個(gè)信號(hào)。每個(gè)get()調(diào)用得到一個(gè)任務(wù)，接下來task_done()調(diào)用告訴隊(duì)列該任務(wù)已經(jīng)處理完畢。

Queue.join() 實(shí)際上意味著等到隊(duì)列為空，再執(zhí)行別的操作【線程阻塞，直到隊(duì)列中的所有任務(wù)處理完畢】

from Queue import Queue,LifoQueue,PriorityQueue
#先進(jìn)先出隊(duì)列
q=Queue(maxsize=5)
#后進(jìn)先出隊(duì)列
lq=LifoQueue(maxsize=6)
#優(yōu)先級(jí)隊(duì)列
pq=PriorityQueue(maxsize=5)
 
for i in range(5):
    q.put(i)
    lq.put(i)
    pq.put(i)
    
print "先進(jìn)先出隊(duì)列：%s;是否為空：%s；多大,%s;是否滿,%s" %(q.queue,q.empty(),q.qsize(),q.full())
print "后進(jìn)先出隊(duì)列：%s;是否為空：%s;多大,%s;是否滿,%s" %(lq.queue,lq.empty(),lq.qsize(),lq.full())
print "優(yōu)先級(jí)隊(duì)列：%s;是否為空：%s,多大,%s;是否滿,%s" %(pq.queue,pq.empty(),pq.qsize(),pq.full())
 
print q.get(),lq.get(),pq.get()
 
print "先進(jìn)先出隊(duì)列：%s;是否為空：%s；多大,%s;是否滿,%s" %(q.queue,q.empty(),q.qsize(),q.full())
print "后進(jìn)先出隊(duì)列：%s;是否為空：%s;多大,%s;是否滿,%s" %(lq.queue,lq.empty(),lq.qsize(),lq.full())
print "優(yōu)先級(jí)隊(duì)列：%s;是否為空：%s,多大,%s;是否滿,%s" %(pq.queue,pq.empty(),pq.qsize(),pq.full())

4、python的四種隊(duì)列操作

①LILO： 先進(jìn)先出，只能在尾部插入元素，只能從頭部取出元素

from queue import Queue
q = Queue()    # 創(chuàng)建隊(duì)列對(duì)象
q.put(1)       # 隊(duì)列尾部插入元素
q.put(2)
q.put(3)
print(q.queue) # 查看隊(duì)列中的所有元素
a = q.get()    # 返回并刪除隊(duì)列頭部元素
print(a)
print(q.queue) # 運(yùn)行結(jié)果deque([2,3])

②LIFO：先進(jìn)后出，類似棧

from queue import LifoQueue
lifoQueue = LifoQueue()  # 創(chuàng)建對(duì)象
lifoQueue.put(1)
lifoQueue.put(2)
lifoQueue.put(3)
print(lifoQueue.queue)
lifoQueue.get()          # 返回并刪除隊(duì)列尾部元素
print(lifoQueue.queue)   # 運(yùn)行結(jié)果[1,2]

③優(yōu)先隊(duì)列：隊(duì)列元素為元組類型，即(優(yōu)先級(jí)，數(shù)據(jù))。

from queue import PrioritQueue as pq
pq = pq()        # 創(chuàng)建有限隊(duì)列
pq.put(1)
pq.put(4)
pq.put(3)  
print(pq.queue)  # 運(yùn)行結(jié)果[1,3,4]
pq.get()         # 返回并刪除優(yōu)先級(jí)最低的元素
print(pq.queue)  # 運(yùn)行結(jié)果[3,4]

④雙端隊(duì)列

>>> from collections import deque   #雙端隊(duì)列
>>> dequeQueue = deque(['Eric','John','Smith'])
>>> print(dequeQueue)
deque(['Eric', 'John', 'Smith'])
>>> dequeQueue.append('Tom')    #在右側(cè)插入新元素
>>> dequeQueue.appendleft('Terry')  #在左側(cè)插入新元素
>>> print(dequeQueue)
deque(['Terry', 'Eric', 'John', 'Smith', 'Tom'])
>>> dequeQueue.rotate(2)    #循環(huán)右移2次
>>> print('循環(huán)右移2次后的隊(duì)列',dequeQueue)
循環(huán)右移2次后的隊(duì)列 deque(['Smith', 'Tom', 'Terry', 'Eric', 'John'])
>>> dequeQueue.popleft()    #返回并刪除隊(duì)列最左端元素
'Smith'
>>> print('刪除最左端元素后的隊(duì)列：',dequeQueue)
刪除最左端元素后的隊(duì)列： deque(['Tom', 'Terry', 'Eric', 'John'])
>>> dequeQueue.pop()    #返回并刪除隊(duì)列最右端元素
'John'
>>> print('刪除最右端元素后的隊(duì)列：',dequeQueue)
刪除最右端元素后的隊(duì)列： deque(['Tom', 'Terry', 'Eric'])

堆、棧、隊(duì)列之間的區(qū)別

1、堆是在程序運(yùn)行時(shí)，而不是在程序編譯時(shí)，申請(qǐng)某個(gè)大小的內(nèi)存空間。即動(dòng)態(tài)分配內(nèi)存，對(duì)其訪問和對(duì)一般內(nèi)存的訪問沒有區(qū)別。

2、棧就是一個(gè)桶，后放進(jìn)去的先拿出來，它下面本來有的東西要等它出來之后才能出來。（后進(jìn)先出）

3、隊(duì)列只能在隊(duì)頭做刪除操作,在隊(duì)尾做插入操作.而棧只能在棧頂做插入和刪除操作。（先進(jìn)先出）

到此這篇關(guān)于Python中堆、棧、隊(duì)列之間的區(qū)別小結(jié)的文章就介紹到這了,更多相關(guān)Python 堆 棧 隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論