python栈，队列, deque

python 数据结构

• 队列，栈 都可以直接使用deque 来实现。
  

  
  

• • deque
• list 实现
• • 队列
  • 栈
• collections模块实现栈和队列

队列，栈 都可以直接使用deque 来实现。

deque

Python的deque模块可以实现队列，并且支持双向队列：

from collections import deque

li = [1,2,3,4]
queue = deque(li) # 从列表创建双向队列（也可以直接创建）
queue.append(5)  # deque([1, 2, 3, 4, 5])
queue.popleft()  # deque([2, 3, 4, 5])

# 双向队列对首进队，队尾出对
queue.appendleft('a')  # deque(['a', 2, 3, 4, 5])
queue.pop()  # deque(['a', 2, 3, 4])

https://blog.csdn.net/Ayhan_huang/article/details/78526442
http://c.biancheng.net/view/5771.html
https://blog.csdn.net/qq_44514871/article/details/104096128

https://cloud.tencent.com/developer/article/1160868
.popleft()
.pop()
.appendleft()
.append()
.remove
list(dq) # 转化到list
dq(list) # list 创建 dq

list 实现

使用 list 列表模拟队列功能的实现方法是，定义一个 list 变量，存入数据时使用 insert() 方法，设置其第一个参数为 0，即表示每次都从最前面插入数据；读取数据时，使用 pop() 方法，即将队列的最后一个元素d出。

如此 list 列表中数据的存取顺序就符合“先进先出”的特点。

实现代码如下：

队列

通过 insert() 方法实现，这种方法效率不高

#定义一个空列表，当做队列
queue = []
#向列表中插入元素
queue.insert(0,1)
queue.insert(0,2)
queue.insert(0,"hello")
print(queue)
print("取一个元素：",queue.pop())
print("取一个元素：",queue.pop())
print("取一个元素：",queue.pop())

运行结果为：
[‘hello’, 2, 1]
取一个元素： 1
取一个元素： 2
取一个元素： hello

栈

使用 list 列表模拟栈功能的实现方法是，使用 append() 方法存入数据；使用 pop() 方法读取数据。

append() 方法向 list 中存入数据时，每次都在最后面添加数据，这和前面程序中的 insert() 方法正好相反。

举个例子：

#定义一个空 list 当做栈
stack = []
stack.append(1)
stack.append(2)
stack.append("hello")
print(stack)
print("取一个元素：",stack.pop())
print("取一个元素：",stack.pop())
print("取一个元素：",stack.pop())

输出结果为：
[1, 2, ‘hello’]
取一个元素： hello
取一个元素： 2
取一个元素： 1

collections模块实现栈和队列

前面使用 list 实现队列的例子中，插入数据的部分是通过 insert() 方法实现的，这种方法效率并不高，因为每次从列表的开头插入一个数据，列表中所有元素都得向后移动一个位置。

这里介绍一个相对更高效的方法，即使用标准库的 collections 模块中的 deque 结构体，它被设计成在两端存入和读取都很快的特殊 list，可以用来实现栈和队列的功能。

举个例子：

from collections import deque 

queueAndStack = deque()
queueAndStack.append(1)
queueAndStack.append(2)
queueAndStack.append("hello")
print(list(queueAndStack))

#实现队列功能，从队列中取一个元素，根据先进先出原则，这里应输出 1
print(queueAndStack.popleft())
#实现栈功能，从栈里取一个元素，根据后进先出原则，这里应输出 hello
print(queueAndStack.pop())
#再次打印列表
print(list(queueAndStack))

输出结果为：
[1, 2, ‘hello’]
1
hello
[2]