Python中堆、栈、队列之间的区别

永远有福

一、队列概念

1、队列是只有一端可以进行插入操作，而另一端可以进行删除操作的有序线性存储结构，满足先进先出的约束。
2、在计算机科学中，队列是一个集合，其中集合中的实体按顺序保存，集合上的主要（或唯一）操作是向后端位置添加实体，称为入队，前端位置并删除实体，称为出队。这使得队列成为先进先出（FIFO）数据结构。在FIFO数据结构中，添加到队列的第一个元素将是第一个要删除的元素。这相当于一旦添加新元素，在删除新元素之前必须删除之前添加的所有元素的要求。通常偷看或还输入了前面的操作，返回前面元素的值而不使其出列。队列是线性数据结构的示例，或者更抽象地是顺序集合。
3、队列提供计算机科学，运输和运营研究中的服务，其中存储和保存诸如数据，对象，人或事件的各种实体以便稍后处理。在这些上下文中，队列执行缓冲区的功能。队列在计算机程序中很常见，它们被实现为与访问例程耦合的数据结构，作为抽象数据结构或作为类的面向对象语言。常见的实现是循环缓冲区和链表。

• 生活中典型的实例就是排队，先到的人排在前面，可先得到服务，后到的人排在后面，并且不能插队。
  
• 计算机应用中典型的实例就是打印机，先发送的打印任务可以先被执行，之后的都要排队等候
  

二、Python实现

1、在 Python 中，和栈一样，同样可以用列表作为队列的底层实现，只需要确定列表的哪一端作为队列的头，也即删除操作端（先进先出），哪一端作为队列的尾，也即插入操作端（后进后出）。同时，把队列抽象为类，队列的先进先出操作实现为类的方法。
2、从理论上讲，队列的一个特征是它没有特定的容量。无论已包含多少元素，始终可以添加新元素。它也可以是空的，此时在再次添加新元素之前删除元素是不可能的。
3、队列的Python实现：
Queue.qsize() 返回队列的大小
Queue.empty() 如果队列为空，返回True,反之False
Queue.full() 如果队列满了，返回True,反之False，Queue.full 与 maxsize 大小对应
Queue.get()从队列中移除并返回数据
Queue.get_nowait() 相当于Queue.get(False)，非阻塞方法
Queue.put(item[, block[, timeout]])
将item放入队列

• timeout为正整数时，等待超时则抛出Full异常
  
• block为False时，有空间可将数据放入队列，立即抛出Full异常
  

Queue.task_done() 在完成一项工作之后，Queue.task_done()函数向任务已经完成的队列发送一个信号。每个get()调用得到一个任务，接下来task_done()调用告诉队列该任务已经处理完毕。
Queue.join() 实际上意味着等到队列为空，再执行别的操作【线程阻塞，直到队列中的所有任务处理完毕】

1. from Queue import Queue,LifoQueue,PriorityQueue
2. #先进先出队列
3. q=Queue(maxsize=5)
4. #后进先出队列
5. lq=LifoQueue(maxsize=6)
6. #优先级队列
7. pq=PriorityQueue(maxsize=5)
9. for i in range(5):
10.     q.put(i)
11.     lq.put(i)
12.     pq.put(i)
13.    
14. print "先进先出队列：%s;是否为空：%s；多大,%s;是否满,%s" %(q.queue,q.empty(),q.qsize(),q.full())
15. print "后进先出队列：%s;是否为空：%s;多大,%s;是否满,%s" %(lq.queue,lq.empty(),lq.qsize(),lq.full())
16. print "优先级队列：%s;是否为空：%s,多大,%s;是否满,%s" %(pq.queue,pq.empty(),pq.qsize(),pq.full())
18. print q.get(),lq.get(),pq.get()
20. print "先进先出队列：%s;是否为空：%s；多大,%s;是否满,%s" %(q.queue,q.empty(),q.qsize(),q.full())
21. print "后进先出队列：%s;是否为空：%s;多大,%s;是否满,%s" %(lq.queue,lq.empty(),lq.qsize(),lq.full())
22. print "优先级队列：%s;是否为空：%s,多大,%s;是否满,%s" %(pq.queue,pq.empty(),pq.qsize(),pq.full())

复制代码

4、python的四种队列操作
①LILO： 先进先出，只能在尾部插入元素，只能从头部取出元素

1. from queue import Queue
2. q = Queue()    # 创建队列对象
3. q.put(1)       # 队列尾部插入元素
4. q.put(2)
5. q.put(3)
6. print(q.queue) # 查看队列中的所有元素
7. a = q.get()    # 返回并删除队列头部元素
8. print(a)
9. print(q.queue) # 运行结果deque([2,3])

复制代码

②LIFO：先进后出，类似栈

1. from queue import LifoQueue
2. lifoQueue = LifoQueue()  # 创建对象
3. lifoQueue.put(1)
4. lifoQueue.put(2)
5. lifoQueue.put(3)
6. print(lifoQueue.queue)
7. lifoQueue.get()          # 返回并删除队列尾部元素
8. print(lifoQueue.queue)   # 运行结果[1,2]

复制代码

③优先队列：队列元素为元组类型，即(优先级，数据)。

1. from queue import PrioritQueue as pq
2. pq = pq()        # 创建有限队列
3. pq.put(1)
4. pq.put(4)
5. pq.put(3)  
6. print(pq.queue)  # 运行结果[1,3,4]
7. pq.get()         # 返回并删除优先级最低的元素
8. print(pq.queue)  # 运行结果[3,4]

复制代码

④双端队列

1. #学习中遇到问题没人解答？小编创建了一个Python学习交流群：531509025
2. >>> from collections import deque   #双端队列
3. >>> dequeQueue = deque(['Eric','John','Smith'])
4. >>> print(dequeQueue)
5. deque(['Eric', 'John', 'Smith'])
6. >>> dequeQueue.append('Tom')    #在右侧插入新元素
7. >>> dequeQueue.appendleft('Terry')  #在左侧插入新元素
8. >>> print(dequeQueue)
9. deque(['Terry', 'Eric', 'John', 'Smith', 'Tom'])
10. >>> dequeQueue.rotate(2)    #循环右移2次
11. >>> print('循环右移2次后的队列',dequeQueue)
12. 循环右移2次后的队列 deque(['Smith', 'Tom', 'Terry', 'Eric', 'John'])
13. >>> dequeQueue.popleft()    #返回并删除队列最左端元素
14. 'Smith'
15. >>> print('删除最左端元素后的队列：',dequeQueue)
16. 删除最左端元素后的队列： deque(['Tom', 'Terry', 'Eric', 'John'])
17. >>> dequeQueue.pop()    #返回并删除队列最右端元素
18. 'John'
19. >>> print('删除最右端元素后的队列：',dequeQueue)
20. 删除最右端元素后的队列： deque(['Tom', 'Terry', 'Eric'])

复制代码

堆、栈、队列之间的区别

1、堆是在程序运行时，而不是在程序编译时，申请某个大小的内存空间。即动态分配内存，对其访问和对一般内存的访问没有区别。
2、栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来。（后进先出）
3、队列只能在队头做删除操作,在队尾做插入操作.而栈只能在栈顶做插入和删除操作。（先进先出）

来源:https://www.cnblogs.com/python1111/p/18360962
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！