python 栈和队列的基本实现

python中的列表结构可以用来实现栈和队列。

【栈】：

　　栈是一种数据结构，具有先入后出的特点，并且栈的所有操作只能在某一端进行，能进行操作的一端的第一个元素称为栈顶，另一端的第一个元素称为栈底

　　栈的五种基本方法：

　　　　push： 元素进栈

　　　　pop： 元素出栈，删除栈顶元素，并返回该元素

　　　　isEmpty： 判断栈是否为空；栈为空，返回True；栈不为空，返回False

　　　　peek： 访问栈顶元素

　　　　length： 返回栈中元素的个数

 1 class Stack():
 2     def __init__(self):
 3         self.stack = []
 4 
 5     def push(self, data):
 6         self.stack.append(data)
 7 
 8     def pop(self):
 9         if not self.isEmpty():
10             return self.stack.pop()
11         else:
12             print('StackError: fail to pop, the stack is empty.')
13 
14     def isEmpty(self):
15         return self.length() == 0
16 
17     def peek(self):
18         if not self.isEmpty():
19             return self.stack[-1]
20         else:
21             print("The stack is empty.")
22 
23     def length(self):
24         return len(self.stack)

【队列】：

　　队列是一种数据结构，具有先入先出的特点，元素的插入和删除分别在不同的端进行，能够插入元素的队列一端称为队尾，另一端只能删除元素，称为队首

　　队列的五种基本操作：

　　　　push： 从队尾插入元素

　　　　pop： 从队首删除元素

　　　　isEmpty： 判断队列是否为空

　　　　peek： 访问队首元素

　　　　length： 获取队列中元素个数

 1 class Queue():
 2     def __init__(self):
 3         self.queue = []
 4 
 5     def push(self, data):
 6         self.queue.append(data)
 7 
 8     def pop(self):
 9         if not self.isEmpty():
10             return self.queue.pop(0)
11         else:
12             print('StackError: fail to pop, the stack is empty.')
13 
14     def isEmpty(self):
15         return self.length() == 0
16 
17     def peek(self):
18         if not self.isEmpty():
19             return self.queue[0]
20         else:
21             print("The queue is empty.")
22 
23     def length(self):
24         return len(self.queue)

【双端队列】：

　　deque模块是Python标准库collections中的一个内置模块，实现双端队列的功能，在队列的两端都可以进行插入和删除

　　使用list存储数据时，按索引访问元素很快，但是插入和删除元素就很慢了，因为list是线性存储，数据量大的时候，插入和删除效率很低。

　　deque是为了高效实现插入和删除操作的双向列表，适合用于队列和栈：

　　deque的种基本操作：

　　　　append： 入队，从队列右端插入一个元素

　　　　appendleft： 入队，从队列左端删除一个元素

　　　　extend： 迭代处理其输入，对每个元素完成与append()相同的处理

　　　　extendleft： 迭代处理其输入，对每个元素完成与appendleft()相同的处理

　　　　pop： 出队，从队列右端删除一个元素，并返回该元素

　　　　popleft： 出队，从队列左端删除一个元素，并返回该元素

　　　　rotate：将队列的某些元素按某一方向进行旋转

 1 from collections import deque
 2 queue = deque() 
 3 queue = deque(maxlen=n)   # 限制queue的最大长度为n 
 4 queue.append('one')       # deque(['one'])
 5 queue.appendleft('two')   # deque(['two', 'one'])
 6 queue.extend('three')     # deque(['two', 'one', 't', 'h', 'r', 'e', 'e'])
 7 queue.extendleft('four')  # deque(['r', 'u', 'o', 'f', 'two', 'one', 't', 'h', 'r', 'e', 'e'])
 8 queue.pop()               # deque(['r', 'u', 'o', 'f', 'two', 'one', 't', 'h', 'r', 'e'])
 9 queue.popleft()           # deque(['u', 'o', 'f', 'two', 'one', 't', 'h', 'r', 'e'])
10 queue.rotate(2)           # deque(['r', 'e', 'u', 'o', 'f', 'two', 'one', 't', 'h']) ，参数为正数n时，将右端的n个元素依次插入到左端
11 queue.rotate(-3)          # deque(['o', 'f', 'two', 'one', 't', 'h', 'r', 'e', 'u']) ，参数为负数n时，将左端的n个元素依次插入到右端

参考博文：　https://www.jb51.net/article/88139.htm

　　　　　　https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/001431953239820157155d21c494e5786fce303f3018c86000

　　　　　https://docs.python.org/3/library/collections.html#collections.deque