栈
定义
栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作，因而按照 后进先出（LIFO, Last In First Out） 的原理运作。
代码实现
class Stack(object):
def __init__(self):
self._list = []
def push(self, item): # 添加一个新的元素item到栈顶
self._list.append(item) # 时间复杂度，列表容器选择尾部为栈顶，时间复杂度为O(1)
def pop(self): # 弹出栈顶元素
return self._list.pop()
def peek(self): # 返回栈顶元素
if self._list:
return self._list[-1]
else:
return None
def is_empty(self): # 判断栈是否为空
return self._list == []
# return not self._list
def size(self): # 返回栈的元素个数
return len(self._list)
if __name__ == "__main__":
s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
print(s.pop())
print(s.pop())
print(s.pop())
print(s.pop())
运行结果：
4
3
2
1
队列
定义
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种 先进先出的（First In First Out） 的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。
队列代码实现
class Queue:
def __init__(self):
self._list = []
def enqueue(self, item): # 添加
self._list.append(item)
def dequeue(self): # 删除
return self._list.pop(0)
def is_empty(self): # 判空
return self._list == []
def size(self): # 返回队列大小
return len(self._list)
if __name__ == "__main__":
s = Queue()
s.enqueue(1)
s.enqueue(2)
s.enqueue(3)
s.enqueue(4)
print(s.dequeue())
print(s.dequeue())
print(s.dequeue())
print(s.dequeue())
运行结果：
1
2
3
4
双端队列定义
双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
代码实现
class Deque: # 双端队列
def __init__(self):
self._list = []
def add_front(self, item): # 添加
self._list.insert(0,item)
def add_rear(self, item): # 删除
self._list.append(item)
def pop_front(self): # 从队列头部删除1个元素
return self._list.pop(0)
def pop_rear(self): # 从队列尾部删除1个元素
return self._list.pop()
def is_empty(self): # 判空
return self._list == []
def size(self): # 返回队列大小
return len(self._list)
if __name__ == "__main__":
deque = Deque()
deque.add_front(1)
deque.add_front(2)
deque.add_rear(3)
deque.add_rear(4)
print(deque.size())
print(deque.pop_front())
print(deque.pop_front())
print(deque.pop_rear())
print(deque.pop_rear())
运行结果：
4
2
1
4
3
排序
排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定顺序进行排列的一种算法
排序的稳定性
稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
冒泡排序
定义
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码实现
def bubble_sort(alist):
n = len(alist)
for j in range(n-1):
for i in range(0,n-1-j):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
if __name__ =="__main__":
li =[54,26,93,17,77,31,44,55,20]
print(li)
bubble_sort(li)
print(li)
运行结果：
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[26, 54, 17, 77, 31, 44, 55, 20, 93]
时间复杂度
最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
最坏时间复杂度：O(n2)
稳定性：稳定
选择排序
定义
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
代码实现
def select_sort(alist):
n = len(alist)
# ok
for j in range(0, n-1 ):
min_index = j
for i in range(j+1, n):
if alist[min_index] > alist[i]:
min_index = i
alist[j], alist[min_index] = alist[min_index], alist[j]
if __name__ == '__main__':
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
select_sort(li)
print(li)
运行结果：
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
时间复杂度
最优时间复杂度：O(n2)
最坏时间复杂度：O(n2)
稳定性：不稳定（考虑升序每次选择最大的情况）
插入排序
定义
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
代码实现
def insert_sort(alist):
n = len(alist)
for i in range(1, n):
while i > 0:
if alist[i] < alist[i-1]:
alist[i], alist[i-1] = alist[i-1], alist[i]
i -= 1
else:
break
if __name__ == '__main__':
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
insert_sort(li)
print(li)
运行结果：
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
时间复杂度
最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
最坏时间复杂度：O(n2)
稳定性：稳定