栈&队列&堆&双端队列

栈

栈是一种后进先出的数据结构，我们可以借助list来实现栈

stack = []
stack.append(item1) # 入栈
stack.pop() # 出栈，返回结果是出栈元素
peak = stack[-1] # 返回栈顶元素

队列

队列是一种先进先出的数据结构，我们可以借助list来实现队列

queue = []
queue.append(item) # 入队
queue.pop(0) # 出队，返回结果是出队元素

堆

• 使用二叉树来表示堆
• 二叉堆是一棵完全二叉树
• 堆中某个节点的值总是不大于其父节点的值，称为最大堆

heapq模块提供了堆的实现，默认是最小堆。queue模块中的优先队列PriorityQueue就是基于heapq模块实现的

import heapq

heap = [] # 定义一个数组，元素是按照完全二叉树的结构存放在数组中的
heapq.heappush(heap,2)
heapq.heappush(heap,4)
heapq.heappush(heap,3)
print(heap)  # [2, 4, 3]
print(heapq.heappop(heap)) # 默认是最小堆，弹出最小元素
mylist = [4,2,6]
heapq.heapify(mylist) # 将数组转变成最小堆
print(mylist) # [2, 4, 6]

如何将最小堆转成最大堆呢？其实只用对元素取负，按照最小堆的方式存储，取出来的值只要再取负，就是最大值了。即push(e)改为push(-e)，pop(e)为-pop(e)

双端队列

双端队列（deque，全名double-endedqueue）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

Python中双端队列的操作函数；

1. 先调用模块 ：from collections import deque #首先从collections 模块中导入deque类
2. 定义一个双端队列和操作

- A=deque() #创建一个空的双队列
- A.append(n) #从右边像队列中增加元素 ，n表示增加的元素
- A.appendleft(n) #从左边像队列中增加元素，n表示增加的元素
- A.clear() #清空队列
- A.count(n) #在队列中统计元素的个数，n表示统计的元素
- A.extend(n) #从右边扩展队列，n表示扩展的队列
- A.extendleft(n) #从左边扩展队列，n表示扩展的队列
- A.pop() #从队列的右边删除元素，并且返回删除值
- A.popleft() #从队列的左边删除元素，并且返回删除值
- A[0] # 获取队首元素(左边第一个)
- A[-1] # 获取队尾元素(右边第一个)