Python程序实现栈

栈是一种先进后出（Last In First Out）的数据结构，可以对数据进行压入（push）和弹出（pop）操作。在Python中，我们可以用list或者deque（双端队列）来实现栈的功能。

更多Python相关文章，请阅读：Python 教程

用list实现栈

基于list实现栈的方式比较简单，我们可以用append()方法向栈中添加元素，使用pop()方法从栈中弹出元素。

示例代码：

stack = []  # 创建一个空list作为栈

stack.append(1)
stack.append(2)
stack.append(3)

print('栈中的元素:', stack)

print('弹出元素:', stack.pop())
print('弹出元素:', stack.pop())

print('栈中的元素:', stack)

输出结果：

栈中的元素: [1, 2, 3]  
弹出元素: 3  
弹出元素: 2  
栈中的元素: [1]  

用deque实现栈

如果我们希望在实现栈的功能时，不仅支持从栈顶进行操作，也可以从栈底进行操作，那么使用deque会更加方便。deque是Python标准库中collections模块的一个数据类型，支持从头部和尾部的插入和删除操作。

示例代码：

from collections import deque

stack = deque()

stack.append(1)
stack.append(2)
stack.append(3)

print('栈中的元素:', stack)

print('弹出元素:', stack.pop())
print('弹出元素:', stack.pop())

print('栈中的元素:', stack)

输出结果：

栈中的元素: deque([1, 2, 3])  
弹出元素: 3  
弹出元素: 2  
栈中的元素: deque([1])  

性能比较

虽然list本身也是支持pop()和append()方法的，但是在实际中使用时，使用deque作为栈的数据结构，总的效率会更高。

我们可以使用Python的timeit模块，来进行比较deque和list的运行时间。

示例代码：

from collections import deque
import timeit

stack1 = deque()
stack2 = []

for i in range(10000):
    stack1.append(i)
    stack2.append(i)

t1 = timeit.timeit("stack1.pop()", setup="from __main__ import stack1", number=10000)
t2 = timeit.timeit("stack2.pop()", setup="from __main__ import stack2", number=10000)

print("deque用时：", t1)
print("list用时：", t2)

输出结果：

deque用时： 0.0005130720000304948  
list用时： 0.0029871830000440887  

结论

在实现栈的过程中，我们可以使用list或者deque来实现，而deque相对于list的效率更高。通过本文的示例，大家可以更好的理解栈的实现过程，也学会了如何使用Python中的deque来实现栈的功能。