1、数据结构与算法（Python）

数据结构和算法是什么？答曰：兵法！

1.1算法的概念

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

• ==算法是独立存在的一种解决问题的方法和思想==。====

对于算法而言，实现的语言并不重要，重要的是思想。

算法可以有不同的语言描述实现版本（如C描述、C++描述、Python描述等），我们现在是在用Python语言进行描述实现。

算法的五大特性

1. 输入: 算法具有0个或多个输入
2. 输出: 算法至少有1个或多个输出
3. 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
4. 确定性：算法中的每一步都有确定的含义，不会出现二义性
5. 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成

1.2第一次尝试

需求：已知a+b+c=1000 a2+b2=c2 求a,b,c可能的值

import time

start_time = time.time()

# 注意是三重循环
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a**2 + b**2 == c**2 and a+b+c == 1000:
                print("a, b, c: %d, %d, %d" % (a, b, c))

end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")

运行结果：
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
elapsed: 214.583347
complete!
注意运行的时间: 160.913325秒
我的电脑运行了大概26min。。。

1.3第二次尝试

import time

start_time = time.time()

# 注意是两重循环
for a in range(0, 1001):
    for b in range(0, 1001-a):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print("a, b, c: %d, %d, %d" % (a, b, c))

end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")

运行结果：
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
elapsed: 0.182897
complete!
注意运行的时间: 0.609427秒

1.4算法效率衡量

1.4.1执行时间反应算法效率

对于同一问题，我们给出了两种解决算法，在两种算法的实现中，我们对程序执行的时间进行了测算，发现两段程序执行的时间相差悬殊（160.913325秒相比于0.609427秒），由此我们可以得出结论：实现算法程序的执行时间可以反应出算法的效率，即算法的优劣。

1.4.2单靠时间值绝对可信吗？

假设我们将第二次尝试的算法程序运行在一台配置古老性能低下的计算机中，情况会如何？很可能运行的时间并不会比在我们的电脑中运行算法一的160.913325秒快多少。
==单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的！==

程序的运行离不开计算机环境（包括硬件和操作系统），这些客观原因会影响程序运行的速度并反应在程序的执行时间上。那么如何才能客观的评判一个算法的优劣呢？

1.4.3时间复杂度与“大O记法”

我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就代表会花费多少时间单位。算然对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，由此可以忽略机器环境的影响而客观的反应算法的时间效率。

对于算法的时间效率，我们可以用“大O记法”来表示。

“大O记法”：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。

时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n)

1.4.4如何理解“大O记法”

对于算法进行特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为3n2和100n2属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率“差不多”，都为n2级。

1.4.5最坏时间复杂度

分析算法时，存在几种可能的考虑：

1. 算法完成工作最少需要多少基本操作，即最优时间复杂度
2. 算法完成工作最多需要多少基本操作，即最坏时间复杂度
3. 算法完成工作平均需要多少基本操作，即平均时间复杂度

对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。
对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。
对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。

• ==因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。==

1.4.6时间复杂度的几条基本计算规则

1. 基本操作，即只有常数项，认为其时间复杂度为O(1)
2. 顺序结构，时间复杂度按加法进行计算
3. 循环结构，时间复杂度按乘法进行计算
4. 分支结构，时间复杂度取最大值
5. 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
6. 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

1.4.7算法分析

1. 第一次尝试的算法核心部分
   时间复杂度：
   T(n) = O(nnn) = O(n3)
2. 第二次尝试的算法核心部分
   时间复杂度：
   T(n) = O(nn(1+1)) = O(n*n) = O(n2)

由此可见，我们尝试的第二种算法要比第一种算法的时间复杂度好多的。

2、常见时间复杂度

所消耗的时间从小到大：

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

3、Python内置类型性能分析——timeit模块

timeit模块可以用来测试一小段Python代码的执行速度。

timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)

Timer是测量小段代码执行速度的类。
stmt参数是要测试的代码语句（statment）；
setup参数是运行代码时需要的设置；
timer参数是一个定时器函数，与平台有关。

timeit.Timer.timeit(number=1000000)

Timer类中测试语句执行速度的对象方法。
number参数是测试代码时的测试次数，默认为1000000次。
方法返回执行代码的平均耗时，一个float类型的秒数。

list的操作测试

def test1():
    ls= []
    for i in range(1000):
        ls = ls + [i]

def test2():
    ls = []
    for i in range(1000):
        ls.append(i)

def test3():
    ls = []
    for i in range(1000):
        ls.insert(0,i)

def test4():
    ls = [i for i in range(1000)]

def test5():
   ls = list(range(1000))

from timeit import Timer
t1 = Timer(stmt='test1()',setup='from __main__ import test1')
print('concat',t1.timeit(number=10000),'second')

t2 = Timer(stmt='test2()',setup='from __main__ import test2')
print('append',t2.timeit(number=10000),'second')

t3 = Timer(stmt='test3()',setup='from __main__ import test3')
print('insert',t3.timeit(number=10000),'second')

t4 = Timer(stmt='test4()',setup='from __main__ import test4')
print('list gen',t4.timeit(number=10000),'second')

t5 = Timer(stmt='test5()',setup='from __main__ import test5')
print('list',t5.timeit(number=10000),'second')

运行结果
concat 18.341660484899588 second
append 1.0099177848925684 second
insert 5.361922586350083 second
list gen 0.45405794180203074 second
list 0.18035762155434298 second

pop操作测试

from timeit import Timer
x1 = [x for x in range(2000000)]
t = Timer('x1.pop(0)','from __main__ import x1')
print('pop(0)',t.timeit(number=1000),'second')

x2 = [x for x in range(2000000)]
t = Timer('x2.pop()','from __main__ import x2')
print('pop()',t.timeit(number=1000),'second')

运行结果
pop(0) 2.033923430381945 second
pop() 0.00011084076000633658 second

测试pop操作：从结果可以看出，pop最后一个元素的效率远远高于pop第一个元素

4、数据结构

4.1概念

数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float，char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。

Python给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构叫做Python的内置数据结构，比如列表、元组、字典。而有些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式称之为Python的扩展数据结构，比如栈，队列等。

4.2算法与数据结构的区别

• ==程序 = 数据结构 + 算法==
• 总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体

4.3抽象数据类型(Abstract Data Type)

抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起，进行封装。

引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。

最常用的数据运算有五种：

1. 插入
2. 删除
3. 修改
4. 查找
5. 排序

5、顺序表

在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。

这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。

根据线性表的实际存储方式，分为两种实现模型：

1. 顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。
2. 链表，将元素存放在通过链接构造起来的一系列存储块中。

5.1顺序表的结构与实现

一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。

5.2顺序表的两种基本实现方式

1. 一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。
   一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。
2. 为分离式结构，表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

元素存储区替换：

1. 一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。
2. 分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。

元素存储区扩充
采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方都不必修改。只要程序的运行环境（计算机系统）还有空闲存储，这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。

扩充的两种策略
每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。

特点：节省空间，但是扩充操作频繁，操作次数多。

每次扩充容量加倍，如每次扩充增加一倍存储空间。

特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。

5.3顺序表的操作

增加元素，删除元素

5.4Python中的顺序表

Python中的list和tuple两种类型采用了顺序表的实现技术，具有前面讨论的顺序表的所有性质。
tuple是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类似。

6、链表

6.1为什么需要链表

• 链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

6.2链表的定义

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

6.3单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

image

• 表元素域elem用来存放具体的数据。
• 链接域next用来存放下一个节点的位置（python中的标识）
• 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

单链表的实现

#定义节点类
class SingleNode(object):
    def __init__(self,item):
        #信息域：存储节点数据的
        self.item = item
        #链接域：链接下一个节点的
        self.next = None


#定义单向链表
class SingleLinkList(object):
    def __init__(self):
        #head:头节点的引用
        self._head = None

    def is_empty(self):
        #链表是否为空
        return self._head == None

    def length(self):
        #链表长度
        count = 0
        #cur指向链表的首节点
        cur = self._head
        #判断cur是否为None
        while cur != None:
            #cur不等于None，就表示一个节点存在
            #给计数器加1
            count += 1
            #cur指向当前节点的下一个节点
            cur = cur.next
        return count

    def travel(self):
        # 遍历整个链表
        # cur指向链表的首节点
        cur = self._head
        # 判断cur是否为None
        while cur != None:
            #打印当前节点的数据
            print(cur.item)
            #cur指向下一个节点
            cur = cur.next

    def add(self,item):
        #链表头部添加元素
        #生成新的节点对象
        node = SingleNode(item)
        #设置node节点的next指向原来的头节点
        node.next = self._head
        #把node节点设置成了新的头节点
        self._head = node

    def append(self,item):
        #链表尾部添加元素
        #定义新的节点
        node = SingleNode(item)
        if self.is_empty():
            self._head = node
        else:
            #cur指向链表的开头
            cur = self._head
            while cur.next != None:
                cur = cur.next
            #cur是链表的最后一个节点
            cur.next = node

    def insert(self,pos, item):
        #指定位置添加元素
        if pos<=0:
            #在链表的头部添加节点
            self.add(item)
        elif pos>=self.length():
            #在链表的尾部添加节点
            self.append(item)
        else:
            node = SingleNode(item)
            #计数器，用来确定插入位置
            count = 0
            cur = self._head
            while count < pos - 1:
                count+=1
                cur = cur.next;
            node.next = cur.next
            cur.next = node

    def remove(self,item):
        #删除节点
        cur = self._head
        #pre:保存cur的上一个节点
        pre = None
        while cur != None:
            if cur.item == item:
                #确定要删除的节点
                if not pre:
                    #删除的是第一个节点
                    #把当前节点的下一个节点当作首节点
                    self._head = cur.next
                else:
                    # 删除的不是第一个节点
                    pre.next = cur.next
                break
            else:
                #不相等，不是要删除的节点
                #遍历下一个节点
                pre = cur
                cur = cur.next

    def search(self,item):
        #查找节点是否存在
        cur = self._head
        while cur != None:
            #判定是不是要查找的节点
            if cur.item == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == '__main__':
    sl = SingleLinkList()
    sl.add(1)
    sl.add(2)
    sl.append(3)
    sl.insert(2,6)
    print('length:',sl.length())
    sl.travel()
    print(sl.search(2))
    sl.remove(2)
    print('length:', sl.length())

链表与顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

6.4单向循环链表

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

单向循环列表的实现

class Node(object):
    """节点"""
    def __init__(self, item):
        self.item = item
        self.next = None


class SinCycLinkedlist(object):
    """单向循环链表"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        """判断链表是否为空"""
        return self._head == None

    def length(self):
        """返回链表的长度"""
        # 如果链表为空，返回长度0
        if self.is_empty():
            return 0
        count = 1
        cur = self._head
        while cur.next != self._head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        if self.is_empty():
            return
        cur = self._head
        print(cur.item)
        while cur.next != self._head:
            cur = cur.next
            print(cur.item)


    def add(self, item):
        """头部添加节点"""
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            #添加的节点指向_head
            node.next = self._head
            # 移到链表尾部，将尾部节点的next指向node
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            #_head指向添加node的
            self._head = node

    def append(self, item):
        """尾部添加节点"""
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            # 移到链表尾部
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            # 将尾节点指向node
            cur.next = node
            # 将node指向头节点_head
            node.next = self._head

    def insert(self, pos, item):
        """在指定位置添加节点"""
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        """删除一个节点"""
        # 若链表为空，则直接返回
        if self.is_empty():
            return
        # 将cur指向头节点
        cur = self._head
        pre = None
        # 若头节点的元素就是要查找的元素item
        if cur.item == item:
            # 如果链表不止一个节点
            if cur.next != self._head:
                # 先找到尾节点，将尾节点的next指向第二个节点
                while cur.next != self._head:
                    cur = cur.next
                # cur指向了尾节点
                cur.next = self._head.next
                self._head = self._head.next
            else:
                # 链表只有一个节点
                self._head = None
        else:
            pre = self._head
            # 第一个节点不是要删除的
            while cur.next != self._head:
                # 找到了要删除的元素
                if cur.item == item:
                    # 删除
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            # cur 指向尾节点
            if cur.item == item:
                # 尾部删除
                pre.next = cur.next

    def search(self, item):
        """查找节点是否存在"""
        if self.is_empty():
            return False
        cur = self._head
        if cur.item == item:
            return True
        while cur.next != self._head:
            cur = cur.next
            if cur.item == item:
                return True
        return False

if __name__ == "__main__":
    ll = SinCycLinkedlist()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print("length:",ll.length())
    ll.travel()
    print(ll.search(3))
    print(ll.search(7))
    ll.remove(1)
    print("length:",ll.length())
    ll.travel()

6.5双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

class Node(object):
    #节点的类
    def __init__(self,item):
        self.item = item
        self.prev = None
        self.next = None

class DLinkList(object):
    #双向链表的类
    def __init__(self):
        #指向链表的头节点
        self._head = None

    def is_empty(self):
        #链表是否为空
        return self._head == None


    def length(self):
        #链表长度
        cur = self._head
        #计数器
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        #遍历链表
        cur = self._head
        while cur != None:
            print(cur.item)
            cur = cur.next

    def add(self,item):
        #链表头部添加
        node = Node(item)
        if self.is_empty():
            #如果是空链表，将_head指向node
            #给链表添加第一个元素
            self._head = node
        else:
            #如果链表不为空，在新的节点和原来的首节点之间建立双向链接
            node.next = self._head
            self._head.prev = node
            #让_head指向链表的新的首节点
            self._head = node


    def append(self,item):
        #链表尾部添加
        #创建新的节点
        node = Node(item)
        if self.is_empty():
            #空链表，
            self._head = node
        else:
            #链表不为空
            cur = self._head
            while cur.next != None:
                cur = cur.next
            #cur的下一个节点是node
            cur.next = node
            #node的上一个节点是
            node.prev = cur

    def insert(self,pos,item):
        #指定位置添加
        if pos <=0:
            self.add(item)
        elif pos > self.length()-1:
            self.append()
        else:
            node = Node(item)
            cur = self._head
            count = 0
            #把cur移动到指定位置的前一个位置
            while count < (pos - 1):
                count+=1
                cur = cur.next
            #node的prev指向cur
            node.prev = cur
            #node的next指向cur的next
            node.next = cur.next
            cur.next.prev = node
            cur.next = node

    def remove(self,item):
        #删除节点
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.item == item:
                #首节点是要删除的节点
                if cur.next == None:
                    #说明链表中只有一个节点
                    self._head = None
                else:
                    #链表多于一个节点的情况
                    cur.next.prev = None
                    self._head = cur.next
            else:
                # 首节点不是要删除的节点
                while cur != None:
                    if cur.item == item:
                        cur.prev.next = cur.next
                        cur.next.prev = cur.prev
                        break
                    cur = cur.next

    def search(self,item):
        #查找节点是否存在
        cur = self._head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False


if __name__ == '__main__':
    dls = DLinkList()
    dls.add(10)
    dls.add(12)
    dls.append(15)
    dls.append(16)
    dls.insert(2,32)
    dls.insert(3,36)
    print('dls lenght:',dls.length())
    dls.travel()
    print(dls.search(15))
    dls.remove(32)
    print('dls length:',dls.length())
    dls.travel()

7、栈

栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

7.1栈结构实现

栈可以用顺序表实现，也可以用链表实现。

7.2栈的操作

class Stack(object):
    #栈的实现
    def __init__(self):
        self.items = []

    def is_empty(self):
        #判断栈是否为空
        return self.items == []

    def push(self,item):
        #压栈：在栈中加入数据元素
        self.items.append(item)

    def pop(self):
        #弹栈操作：从栈中弹出元素
        return self.items.pop()

    def peek(self):
        #返回栈顶的数据元素
        return self.items[len(self.items)-1]

    def size(self):
        #返回栈的尺寸
        return len(self.items)

if __name__ == '__main__':
    stack = Stack()
    print(stack.is_empty())
    stack.push('hello')
    stack.push('python')
    stack.push('qiku')
    stack.push('zhengzhou')
    print(stack.is_empty())
    print(stack.size())
    print(stack.peek())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

8、队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First In First Out）的线性表，简称FIFO。

允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

8.1队列的实现

同栈一样，队列也可以用顺序表或者链表实现。

8.2操作

class Queue(object):
    #队列的实现
    def __init__(self):
        self.items = []

    def is_empty(self):
        #判断队列是否为空
        return self.items == []

    def enqueue(self,item):
        #插入到队列的头部
        self.items.insert(0,item)

    def dequeue(self):
        #删除数据
        return self.items.pop()

    def size(self):
        #返回队列的大小
        return len(self.items)


if __name__ == '__main__':
    q = Queue()
    q.enqueue("hello")
    q.enqueue("sssss")
    q.enqueue("aaaaa")
    print(q.size())
    print(q.is_empty())
    print(q.dequeue())
    print(q.size())
    print(q.dequeue())
    print(q.size())

9、双端队列

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

#双端列表的定义
class Deque(object):
    def __init__(self):
        self.items = []

    def add_front(self,item):
        #从队头加入一个item元素
        self.items.insert(0,item)

    def add_rear(self,item):
        #从队尾加入一个item元素
        self.items.append(item)

    def remove_front(self):
        #从队头删除一个item元素
        return self.items.pop(0)

    def remove_rear(self):
        #从队尾删除一个item元素
        return self.items.pop()

    def is_empty(self):
        #判断双端队列是否为空
        return self.items == []

    def size(self):
        # 返回队列的大小
        return len(self.items)


if __name__ == '__main__':
    deqeue = Deque()
    print(deqeue.is_empty())
    deqeue.add_front(22)
    deqeue.add_front(33)
    deqeue.add_rear(44)
    deqeue.add_rear(55)
    print(deqeue.is_empty())
    print(deqeue.size())
    print(deqeue.remove_front())
    print('size:',deqeue.size())
    print(deqeue.remove_rear())
    print('size:',deqeue.size())

10、排序算法

排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定顺序进行排列的一种算法。

10.1排序算法的稳定性

稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

(4, 1) (3, 1) (3, 7)（5, 6）

在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：

(3, 1) (3, 7) (4, 1) (5, 6) （维持次序）

(3, 7) (3, 1) (4, 1) (5, 6) （次序被改变）

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，（比如上面的比较中加入第二个标准：第二个键值的大小）就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

10.2冒泡排序

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下：

1. 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

def bubble_sort(alist):
    for j in range(len(alist)-1,0,-1):
        # j表示每次遍历需要比较的次数，是逐渐减小的
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)

时间复杂度

• 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
• 最坏时间复杂度：O(n2)
• 稳定性：稳定

10.2选择排序

选择排序（Selection sort）是一种简单直观的排序算法。

它的工作原理如下：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
2. 再从剩余未排序元素中继续寻找最小（大）元素
3. 放到已排序序列的末尾。
4. 以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

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]

alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)

时间复杂度

• 最优时间复杂度：O(n2)
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定（考虑升序每次选择最大的情况）

10.3插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

def insert_sort(alist):
    # 从第二个位置，即下标为1的元素开始向前插入
    for i in range(1, len(alist)):
        # 从第i个元素开始向前比较，如果小于前一个元素，交换位置
        for j in range(i, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]

alist = [54,26,93,17,77,31,44,55,20]
insert_sort(alist)
print(alist)

时间复杂度

• 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
• 最坏时间复杂度：O(n2)
• 稳定性：稳定