python 中的列表作为栈和队列的使用方式

列表作为栈使用

列表提供的方法，让我们很方便的实现后进先出的具有栈特性的操作。要添加一个元素到堆栈的顶端，使用 append() 。要从堆栈顶部取出一个元素，使用 pop() ，不用指定索引

In [9]: stack = [3,4,5,6]

In [10]: stack.append(7)

In [11]: stack
Out[11]: [3, 4, 5, 6, 7]

In [12]: stack.pop()
Out[12]: 7

In [13]: stack
Out[13]: [3, 4, 5, 6]
​

列表作为队列使用

队列的特性是后进后出，一端入队另一端出队，使用 append 队尾添加元素，使用 pop(0) 对首元素出队

In [14]: queue = [5,6,7]

In [15]: queue.append(8)

In [16]: queue
Out[16]: [5, 6, 7, 8]

In [17]: queue.pop(0)
Out[17]: 5

In [18]: queue
Out[18]: [6, 7, 8]
​

但是这种实现方式是比较低效的，pop 的操作时间复杂度是 O(N)的，因为每次队首元素出队后，其他位置的元素都要向前移动一位.
python 中提供了更加高效的队列实现，deque,他是一个双向队列对象，也就是说两端都可以入队和出队，而且时间复杂度都是 O(1).

In [19]: from collections import deque

In [20]: d = deque((4,6,7,8))

In [21]: d
Out[21]: deque([4, 6, 7, 8])

In [22]: d.append(9)

In [23]: d.popleft()
Out[23]: 4

In [24]: d
Out[24]: deque([6, 7, 8, 9])
​

删除列表某个切片

在列表中删除某个切片内的元素一般有两种场景，

• 将指定的切片赋值为空列表

In [25]: a = [3,4,5,6,7]

In [26]: a[2:4] = []

In [27]: a
Out[27]: [3, 4, 7]
​

• 使用 del 语句

In [30]: b = [5,6,7,8,9,0]

In [31]: del b[2:5]

In [32]: b
Out[32]: [5, 6, 0]
​