Python数据结构与算法_第4节_栈 & 队列 & 排序与搜索
栈/堆栈（stack），是一种容器，可存入数据元素、访问元素、删除元素。是一种只允许在容器的一端（栈顶端top）加入数据（push）和输出数据（pop）的运算 。
后进先出（LIFO, Last In First Out）：像只有一个出口的杯子一样，最先被添加的数据会在栈的底部，在读取时最后进入的数据先被读取。
线性表（顺序表、链表）的逻辑和栈一样；线性表描述的是数据怎么存放，栈描述的是操作。在栈中可以运用到链表。
栈可以用顺序表（list）实现，也可以用链表实现。
Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数
# coding: utf-8
class Stack(object):
"""栈"""
def __init__(self):
# 用顺序表来定义栈
self.__list = []
def is_empty(self):
"""判断栈是否为空"""
return self.__list == []
# return not self.__list
def push(self, item):
"""加入一个新的元素item到栈顶"""
# 为了时间复杂度最低，在尾部添加item（O(1)）
self.__list.append(item)
def pop(self):
"""弹出栈顶元素"""
return self.__list.pop()
def peek(self):
"""返回栈顶元素"""
# 如果列表不为空，则返回栈顶元素
if self.__list:
return self.__list[len(-1]
# 如果列表为空，则返回None
else:
return None
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）是只允许在一端插入数据，在另一端删除数据的线性表 。
先进先出（FIFO）：插入数据的一端为队尾，删除数据的一端为对头。队列不允许在中间部位进行操作。
Queue() 创建一个空的队列
enqueue(item) 进入队列，往队列中添加一个item
dequeue() 退出队列，从队列头部删除一个元素
is_empty() 判断一个队列是否为空
size() 返回队列的大小
# coding: utf-8
class Queue(object):
"""队列"""
def __init__(self):
self.__list = []
def is_empty(self):
"""判断一个队列是否为空"""
return self.__list == []
# return not self.__list
def enqueue(self, item):
"""往队列中添加一个item"""
# 1. 在尾部添加O(1)，头部删除O(n)
# 2. 在尾部删除O(1)，头部添加O(n)
# 选择哪一种具体取决于在调用queue时，最常使用的是出队还是入队。
# 尾部添加元素
self.__list.append(item)
# 头部添加元素
# self.__list.insert(0, item)
def dequeue(self):
"""从队列头部删除一个item"""
# 头部删除元素
return self.__list.pop(0)
# 从尾部删除元素
# return self.__list.pop()
def size(self):
"""返回队列的大小"""
return len(self.__list)
if __name__ == "__main__":
s = Stack()
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）：具有队列和栈性质的数据结构。
双端队列中元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
相当于两个栈底部合在一起了。
Deque() 创建一个空的双端队列
add_front(item) 从队头加入一个item元素
add_rear(item) 从队尾加入一个item元素
remove_front() 从队头删除一个item元素
remove_rear() 从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小
# coding: utf-8
class Deque(object):
"""双端队列"""
def __init__(self):
self.__list = []
def is_empty(self):
"""判断队列是否为空"""
return self.__list == []
def add_front(self, item):
"""在队头添加元素"""
self.__list.insert(0,item)
def add_rear(self, item):
"""在队尾添加元素"""
self.__list.append(item)
def remove_front(self):
"""从队头删除元素"""
return self.__list.pop(0)
def remove_rear(self):
"""从队尾删除元素"""
return self.__list.pop()
def size(self):
"""返回队列大小"""
return len(self.__list)
排序算法（sorting algorithm）是一种能将一串数据依照特定顺序进行排列的算法。
稳定性：稳定的排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
ex.不稳定的排序算法得到的是b结果，稳定的排序算法得到的是a结果。
冒泡排序（bubble sorting）：它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的思路：
比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
每次选出前面部分数列的最大值，把它逐渐换置到队尾。
需要进行n-1次冒泡过程，每次对应的比较次数如下图所示：
先写内层循环再写外层循环# 先写内层循环再写外层循环。
# coding:utf-8
def bubble_sort(alist):
# list的index是(0～n-1)，我们需要遍历的index范围为(0~n-2)
n = len(alist)
# 一共循环n-1次
for j in range(0, n-1): # O(n)
# 单次冒泡过程
for i in range(0, n-1-j): # O(n)
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
优化：一旦在某次循环中，发现元素没有发生交换，则说明全部的序列都是有序的，则break。
优化前后，最坏时间复杂度无变化，最优时间复杂度减少。# 先写内层循环再写外层循环。
# coding:utf-8
def bubble_sort(alist):
# list的index是(0～n-1)，我们需要遍历的index范围为(0~n-2)
n = len(alist)
# 一共循环n-1次
for j in range(0, n-1): # O(n)
count = 0
# 单次冒泡过程
for i in range(0, n-1-j): # O(n)
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
count += 1
if count == 0:
break
最优时间复杂度：
O
(
n
)
O(n)
O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
最坏时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
稳定性：稳定
选择排序（selection sorting）：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
对数据的移动比较少，如果该元素位于正确的位置上，则它不会被移动。因此，选择排序最多对n个元素的列表进行n-1次交换。
选择排序算法的思路：
遍历全部无序的元素，找到最小/最大值，把它放到开头/结尾。
重复n-1次。
从后面无序序列中选出最小/最大值，然后把它与开头/结尾的元素互换。重复n-1次。
# coding:utf-8
def selection_sort(alist):
n = len(alist)
# 需要进行n-1次选择操作
for i in range(n-1):
# 记录最小位置
min_index = i
# 从i+1位置到末尾选择出最小数据
for j in range(i+1, n):
if alist[j] < alist[min_index]:
min_index = j
# 如果选择出的数据不在正确位置，进行交换
if min_index != i:
alist[i], alist[min_index] = alist[min_index], alist[i]
最优时间复杂度：O(n2)
最坏时间复杂度：O(n2)
稳定性：不稳定（考虑升序每次选择最大的情况）
插入排序（insertion sorting）：从后面的无须数据中拿出数据，在前面的已排序序列中，从后向前扫描，找到相应位置并插入。在从后向前扫描的过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
与选择排序的区别：
选择排序：**操作的是无序的部分。**前面有序序列的位置固定，从后面的无序序列中选出相应的元素放过去。
插入排序：**操作的是有序的部分。**后面无序序列的元素是固定的，挨个拿出来，来测试出该元素在前面的有序序列中应该放在哪个位置上。
插入排序算法的思路：
把序列中的第一个元素看作为有序序列
把无序序列的第一个元素（此处为列表的第二个元素）放到有序列表中合适的位置。
alist = {93, 54, 77, 31, 44, 55, 226}
alist = {54, 93, 77, 31, 44, 55, 226} # 54比93小
alist = {54, 93, 77, 31, 44, 55, 226} # 空格前面为有序序列，后面为无序序列
alist = {54, 77， 93, 31, 44, 55, 226}
......
# coding:utf-8
def selection_sort(alist):
"""插入排序"""
n = len(alist)
# 从右边的无序序列中取出多少个元素执行这样的过程
for j in range(1, n):
# i = [1, 2, 3, ..., n-1]
# i代表内层循环的起始值
i = j
# 执行从右边的无序序列中去除第一个元素，即i位置的元素，然后将其插入到前面的正确位置中。
while i > 0
if alist[i] < alist[i-1]:
alist[i], alist[i-1] = alist[i-1], alist[i]
i -= 1
如果i位置的元素在正确的位置上，则break
else:
break
最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
最坏时间复杂度：O(n2)
稳定性：稳定