【人生苦短，我学 Python】（13）通过python内置函数实现栈、队列

---

Python 所有文章传送门
【Python】所有文章传送门

---

简述 / 前言

上篇文章讲完了函数部分，这篇文章主要介绍如果通过内置函数（模块）实现常用的数据结构：栈、队列

1. collections 的 deque 对象

collections.deque() 实现的是双端队列，它支持从任意一端增加和删除元素！

操作	含义
dq.append(x)	在右端添加元素x
dq.appendleft(x)	在左端添加元素x
dq.pop()	从右端弹出元素。若队列中无元素，则导致IndexError
dq.popleft()	从左端弹出元素。若队列中无元素，则导致IndexError
dq.extend(iterable)	在右端添加系列iterable中的元素
dq.extendleft(iterable)	在左端添加系列iterable中的元素
dq.remove(value)	移除第一个找到的x。若未找到，则导致IndexError
dq.count(x)	返回元素x在队列中出现的个数
dq.clear()	删除所有元素，即清空队列
dq.reverse ()	反转队列中所有元素
dq.rotate(n)	如果n>0，所有元素向右移动n个位置（循环）；否则向左

2. 栈

栈是后进先出的结构，用双端队列实现。

2.1 栈操作-1

入栈使用 dq.append(x) 操作，出栈使用 dq.pop() 操作！

实现代码如下：

from collections import dequedq = deque()
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
dq.append(5)print(dq.pop())
print(dq.pop())
print(dq.pop())
print(dq.pop())
print(dq.pop())
print(dq.pop())     # 栈为空，引出IndexError

其输出如下：

5
4
3
2
1
Traceback (most recent call last):File "D:\xxxxxx\CSDN.py", line 15, in <module>print(dq.pop())     # 栈为空，引出IndexError
IndexError: pop from an empty deque

为了解决这个问题，我对 pop() 操作进行了修改，修改后的代码如下：

from collections import dequedef deque_pop(dq: deque) -> deque:"""重新实现出栈操作:param dq: 栈:return: 出栈后的栈"""if len(dq) == 0:return deque()else:return dq.pop()dq = deque()
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
dq.append(5)print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))    # 栈为空

其输出如下：

5
4
3
2
1
deque([])

2.2 栈操作-2

因为我们是用双端队列实现的栈，因此还可以换个方向当做栈顶，入栈使用 dq.appendleft(x) 操作，出栈使用 dq.popleft() 操作！

实现代码如下：

from collections import dequedq = deque()
dq.appendleft(1)
dq.appendleft(2)
dq.appendleft(3)
dq.appendleft(4)
dq.appendleft(5)print(dq.popleft())
print(dq.popleft())
print(dq.popleft())
print(dq.popleft())
print(dq.popleft())
print(dq.popleft())     # 栈为空，引出IndexError

其输出如下：

5
4
3
2
1
Traceback (most recent call last):File "D:\xxxxxx\CSDN.py", line 15, in <module>print(dq.popleft())     # 栈为空，引出IndexError
IndexError: pop from an empty deque

为了解决这个问题，我对 popleft() 操作进行了修改，修改后的代码如下：

from collections import dequedef deque_pop(dq: deque) -> deque:"""重新实现出栈操作:param dq: 栈:return: 出栈后的栈"""if len(dq) == 0:return deque()else:return dq.popleft()dq = deque()
dq.appendleft(1)
dq.appendleft(2)
dq.appendleft(3)
dq.appendleft(4)
dq.appendleft(5)print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))    # 栈为空

其输出如下：

5
4
3
2
1
deque([])

3. 队列

队列是先进先出的结构，用双端队列实现。

3.1 队列操作-1

入对使用 dq.append(x) 操作，出对使用 dq.popleft() 操作！

实现代码如下：

from collections import dequedq = deque()
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
dq.append(5)print(dq.popleft())
print(dq.popleft())
print(dq.popleft())
print(dq.popleft())
print(dq.popleft())
print(dq.popleft())     # 队列为空，引出IndexError

其输出如下：

1
2
3
4
5
Traceback (most recent call last):File "D:\xxxxxx\CSDN.py", line 28, in <module>print(dq.popleft())     # 队列为空，引出IndexError
IndexError: pop from an empty deque

为了解决这个问题，我对 popleft() 操作进行了修改，修改后的代码如下：

from collections import dequedef deque_pop(dq: deque) -> deque:"""重新实现出对操作:param dq: 队列:return: 出对后的队列"""if len(dq) == 0:return deque()else:return dq.popleft()dq = deque()
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
dq.append(5)print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))  # 队列为空

其输出如下：

1
2
3
4
5
deque([])

3.2 队列操作-2

同样因为我们是用双端队列实现的栈，因此还可以换个方向当做队头，入对使用 dq.appendleft(x) 操作，出对使用 dq.pop() 操作！

实现代码如下：

from collections import dequedq = deque()
dq.appendleft(1)
dq.appendleft(2)
dq.appendleft(3)
dq.appendleft(4)
dq.appendleft(5)print(dq.pop())
print(dq.pop())
print(dq.pop())
print(dq.pop())
print(dq.pop())
print(dq.pop())     # 队列为空，引出IndexError

其输出如下：

1
2
3
4
5
Traceback (most recent call last):File "D:\xxxxxx\CSDN.py", line 28, in <module>print(dq.pop())     # 队列为空，引出IndexError
IndexError: pop from an empty deque

为了解决这个问题，我对 popleft() 操作进行了修改，修改后的代码如下：

from collections import dequedef deque_pop(dq: deque) -> deque:"""重新实现出对操作:param dq: 队列:return: 出对后的队列"""if len(dq) == 0:return deque()else:return dq.pop()dq = deque()
dq.appendleft(1)
dq.appendleft(2)
dq.appendleft(3)
dq.appendleft(4)
dq.appendleft(5)print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))
print(deque_pop(dq))  # 队列为空

其输出如下：

1
2
3
4
5
deque([])

总结

当然我们也可以自己写一个类来实现栈、队列等数据结构，下一篇文章将会开始介绍python中最重要的一个知识点：面向对象以及类！

不过我们自己写的栈或者队列的运算速度可能没本篇文章介绍的使用 collections.deque() 实现的快，因此以后可以使用这个内置函数来实现一些数据结构，即简单、运算还快！