python数据结构-栈和队列以及算法-排序

栈的特点：

栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。采用LIFO（后进先出）的原理运作

栈的实现：

再栈中添加元素被称之为压栈（push），删除元素被称之为出栈（pop）

class Stack(object): def __init__(self): self.__list = [] def push(self, item): # 添加一个新的元素item到栈顶 self.__list.append(item) 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 == [] def size(self): # 返回栈的元素个数 return len(self.__list)

队列的特点及实现：

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，采用FIFO（先进先出）的原理运作

class Queue(object): # 队列 def __init__(self): self.__list = [] def enqueue(self, item): # 往队列中添加一个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)

双端队列概念及实现：

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

class Deque(object): # 双端队列 def __init__(self): self.__list = [] def add_front(self, item): # 往队列头中添加一个item元素 self.__list.insert(0,item) def add_rear(self, item): # 往队列尾中添加一个item元素 self.__list.append(item) def pop_front(self): # 从队列头部删除一个元素 return self.__list.pop(0) def pop_rear(self): # 从队列尾部删除一个元素 return self.__list.pop() def is_empty(self): # 判断一个队列是否为空 return self.__list == [] def size(self): # 返回队列的大小 return len(self.__list)

排序：

排序的稳定性：排序之后的序列和排序之前的序列相比位置不发生改变，则称之为稳定排序算法

冒泡排序及实现：

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。稳定性：稳定

def bubble_sort(alist): n = len(alist) for j in range(0, n - 1): count = 0 for i in range(0, n - 1 - j): # 第一次循环 if alist[i] > alist[i + 1]: alist[i], alist[i + 1] = alist[i + 1], alist[i] count += 1 if 0 == count: return

选择排序及实现：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。稳定性：不稳定

def sel_sort(alist): n = len(alist) for j in range(0,n-1):#0~n-2 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]

插入排序及实现：

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。稳定性：稳定

def insert_sort(alist): n = len(alist) # 从右边的无序序列中取出多少个元素执行这样的过程 for j in range(1, n): # j=[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 else: break