在python中实现栈

栈是一种线性结构，特点是后进先出。栈中数据的插入和删除都是在栈顶端进行，常见的栈的操作函数为：

1. empty()
2. size()
3. top()
4. push()
5. pop()

python种有3种方式实现栈：

1. list
2. collection.deque
3. queue.LifoQueue

使用列表实现栈：
list中，append()可以向栈顶添加元素，pop()可以以后进先出的方式删除元素，但是列表本身有一定缺点，就是随着列表不断变长，速度会遇到瓶颈，列表是动态数组，可以向其中添加新元素，但是需要分配新空间，因此append需要更长的时间。

使用collections.deque实现栈
python中栈也可以用deque类实现，当我们想要在实现在容器两端更快速地进行append和pop操作时，deque比列表更合适．deque可以提供O(1)时间的append和pop操作，而列表则需要O(n)时间。

>>> from collections import deque
>>> stack = deque()
>>> # append() fuction to push
... #element in list
... 
>>> stack.append('hello')
>>> stack.append('world')
>>> stack.append('!')
>>> print('Initial stack')
Initial stack
>>> print(stack)
deque(['hello', 'world', '!'])
>>> #pop() function to pop element
... #from stack in LIFO order
... 
>>> print('\nElement poped from stack')

Element poped from stack
>>> print(stack.pop())
!
>>> print(stack.pop())
world
>>> print(stack.pop())
hello
>>> print('\nStack after all elements are poped')

Stack after all elements are poped
>>> print(stack)deque([])

使用queue module实现栈
Queue模块有LIFO queue，也就是栈结构．用put()和get()操作从Queue中添加和获得数据

>>> from queue import LifoQueue
>>> stack = LifoQueue(maxsize = 3)
>>> print(stack.qsize())
0
>>> stack.put('hello')
>>> stack.put('world')
>>> stack.put('!')
>>> print('\nElement poped from stack')

Element poped from stack
>>> print(stack.get())
!
>>> print(stack.get())
world
>>> print(stack.get())
hello
>>> print('\nEmpty:', stack.empty())

Empty: True