线性结构的概念

• 线性结构是一种有序数据项的集合，可以有零个或多个数据项，其中每个数据项都有唯一的前驱和后继，除了第一个没有前驱，最后一个没有后继

• 线性表包括列表，栈，队列等不同的抽象数据结构，不同的线性表主要体现在于对于数据项的增删改查的方式以及性能差异

三种主要线性数据结构类型

列表-LIST

• python中包含了一个内建的列表类型，是基于数组进行实现的，但其实还有几种不同的实现方法,下面主要介绍两种经典的实现（数组和链表）

顺序存储（数组实现）

• 底层物理结构是数组，而数组用一段连续的内存存放，所以在内存中数据项是相互挨在一起的，只要知道了此列表在内存地址中的起始位置，就能通关偏移量的大小定位到其他数据项的位置，基于索引

数组两大特点

• 支持随机访问
• 存储在一块连续的内存上

你所要了解的数组操作

增加数组大小

1. 创建一个新的，更大的数组（申请更大的内存空间）
2. 将原数据复制到新的数组中（这样新数组就有更大的空间容纳数据项）
3. 将指向就数组的变量重新指向新数组，旧数组的内存则被回收

减小数组的大小

1. 创建一个更小的数组
2. 将原数组内容复制到新数组
3. 将新数组设置为新的数组对象

数组中插入一项

1. 先检查数组大小是否够用，不够用先申请空间
2. 从数组最后一项的位置开始直到要插入数据项的索引位置，将每个数据项都往后移动一个位置
3. 这样就会在目标位置空出一个位置给新的数据项插入

数组中删除一项

1. 先将目标索引位置的数据项从数组中移除
2. 将索引位置之后的所有数组向前移动一位

时间复杂度

# O(1)
搜索第i项/替换第i项/从末尾追加/从末尾删除/
# O(n)
从第i个位置插入/删除/增加数组容量/减小数组容量

链式存储（链表实现）

特点

• 由于数组结构的列表对于删除和插入的性能不是很好，所以构造了以链表作为底层结构的实现
• 链表结构和数组结构的不同主要体现在每个数据项不光含有数据信息，还另外维护了一个指针元素，这两部分合起来称之为一个节点。而链表实现的基本元素就是节点，单链表的节点包含两个部分，数据项的引用以及到下一个节点的引用
• 链表结构中，对于单纯的数据项，在内存中的相对位置没有规则，但是可以通过每个节点中指针信息指向下一个数据项在内存中的位置，这样就形成链条一样的形状，故称之为链表结构

构建节点类

# 构建节点类
class Node:
  def __init__(self, data, next=None):
    self.data = data
    self.next = next
# 一般来讲，初始化次类会创建一个空链接或是新的Node对象

生成链表

head = None
for i in range(n):
  head = Node(i, head)
# 假设n=3，生成的链表是这个样子的：2->1->0->None，此时head=Node(2,指向数据项为1的节点)
# 你会发现，数据项的遍历和节点生成以相反的方式呈现（当然，这只是一种生成链表的方式，也可以通过程序设计，保证数据项和节点生成的一致性）

链表操作(代码实现)

遍历

# 正确的做法一般来讲，会构建一个新的变量，初始化为链表的head指针，用指针去遍历整个链表
temp = head
while temp !=None:
  temp = temp.next

# 错误的遍历方法，因为head在变化，最后的结果就是，head是None，前面的节点全都删除了
while head !=None:
  head = head.next

搜索目标值

# 构建一个新的变量，初始化为链表的head指针，通过遍历搜索目标值
temp = head
while temp != None and temp.data != target_data:
  probe = probe.next
if probe != None:
  print("success to find")
 else:
  print("fail to find")

替换第i项位置的数据

temp = head
# 假设替换索引为5的节点
index = 5
# 要么遍历到链表结尾，链表长度不够，结束循环，要么找到链表要替换的位置，结束循环
while temp != None and index > 0:
  temp = temp.next
  index -= 1
if temp == None:
  print("fail to replace")
else:
  temp.data = target

在任意索引位置插入节点

# 两种情况，要么索引大于链表长度，那么插在最后，要么索引小于链表，插入索引位置
if head is None or index < 0:
  head= Node(new_data, head)
else:
  temp = head
  # index > 1是为了放置新节点在（index-1）到index之间
  if temp.next != None and index > 1:
    temp = temp.next
    index -= 1
  temp.next = Node(new_data, temp.next)

在任意位置删除节点

# 这里只考虑索引小于链表长度
temp = head
index = 5
while temp.next.next != None and index > 1:
  temp = temp.next
  index -= 1
temp.next = temp.next.next

时间复杂度

# O(1)
从开始处插入节点/从开始处删除节点
# O(n)
在第i个位置访问/替换(平均情况),在第i个位置插入/删除(平均情况)

列表接口

• 一般列表这种结构，都会提供如下几个接口

add(data)               # 添加数据项
insert(index, data)     # 插入数据项到索引位置
replace(index, data)    # 将索引位置的数据项替换
pop(index)              # 将索引位置的数据项弹出列表
remove(data)            # 删除某个数据项

栈-STACK

特点

• 栈结构也可以通过数组或者链表结构设计实现

• 数据项的加入和移除都限制在一端，这个端点一般称之为栈顶

• 后进先出的结构特点（LIFO），越早进入栈结构的数据越晚离开栈

生活中的例子（加深理解）

• 一摞盘子，想取的话只能先取最上面的一个，然后下一个，依次类推，但如果想放新的盘子上去，也只能将新盘子放在所有盘子的最上面，然后再摞一个，以此类推。这个（顶端）用来拿或者取盘子的位置，抽象出来一个概念，称之为栈顶。盘子最下面不参与任何的操作，称之为栈底。

经典应用

• 编译器基本功能中的对于各种括号（"(){}[]"）的正确匹配
• 回溯算法
• 管理计算机内存支持函数和方法的调用
• 中缀表达式转换为后缀表达式；计算后缀表达式
  • 利用运算符优先级的思想（转换）
    1. 如果遇到操作数，我们就直接将其输出
    2. 如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
    3. 如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
    4. 如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "
    5. 如果我们读到了输入的末尾，则将栈中所有元素依次弹出

部分应用代码实现

# 我们这里简单的用python内置列表作为基础结构实现栈结构
class Stack:
    """利用列表（底层为数组）构建栈的抽象结构"""
    def __init__(self):
        self._items = []

    def size(self):
        return len(self._items)

    def push(self, item):
        self._items.append(item)

    def pop(self):
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

    def peek(self):
        return self._items[len(self._items) - 1]
#######################################################################

# 中缀转后缀表达式
def infix_to_suffix(expressions):
    """当前约定中缀表达式是以空格进行分割, exp: a + b * c"""
    s = Stack()
    exp_list = expressions.split(" ")
    # 存放操作数
    num_list = []
    # 自定义优先级，"("的存在是为了有多重括号存在时，保证所有的+-*/都可以顺利入栈
    priority_dic = {"(": 1, "+": 2, "-": 2, "*": 3, "/": 3}
    for token in exp_list:
        if token not in "+-*/()":
            num_list.append(int(token))
        elif token == "(":
            s.push(token)
        elif token == ")":
            while s.peek() != "(":
                num_list.append(s.pop())
            # 将"("弹出
            s.pop()
        else:
            while s.size() > 0 and priority_dic.get(token) <= priority_dic.get(s.peek()):
                num_list.append(s.pop())
            s.push(token)
    # 检查栈中是否还有操作符存在，有的话，依依弹出即可
    while not s.is_empty():
        num_list.append(s.pop())
    return "".join([str(i) for i in num_list])


# 计算后缀
def calc_suffix(expression):
    s = Stack()
    for token in expression:
        if token in "0123456789":
            s.push(int(token))
        else:
            # 要考虑到减法和除法顺序不能颠倒的问题
            num_first = s.pop()
            num_second = s.pop()
            tmp_result = convert_to_math(token, num_first, num_second)
            s.push(tmp_result)
    return s.pop()


# 辅助函数，每两个弹出元素的计算结果
def convert_to_math(token, num1, num2):
    if token == "*":
        return num1 * num2
    elif token == "/":
        return num2 / num1
    elif token == "-":
        return num2 - num1
    elif token == "+":
        return num1 + num2

# 测试数据
convert_ret = infix_to_suffix("3 + 5 * 2 - 5 * ( 3 + 2 )")
calcu_ret = calc_suffix(convert_ret)
print(calcu_ret)
####################################################################

# 10进制转换为2/8/16进制的字符串格式
def to_str(n, base):
    :param n: 十进制数
    :param base: 想要转换的进制
    :return: 
    if n < base:
        return str(n)
    elif 2 <= base <= 10:
        return to_str(n // base, base) + str((n % base))
    else:
        convert_string = "0123456789abcdef"
        return to_str(n // base, base) + convert_string[(n % base)]

ret = to_str(541, 2)
print(ret)

队列-QUEUE

特点

• 队列也可以由数组或是链表结构设计实现，数组的实现（循环数组的方法）要难于链表，但是性能更优

• 队列是一种有次序的数据集合，表现为向队列中添加数据时，永远在尾端添加，而移除数据则永远从队首删除

• 先进先出的结构特点（FIFO），越早进入栈结构的数据越早离开栈

生活中的例子（加深理解）

• 排队买票，一般情况下，你应该从买票队伍的最后一个位置进入列队
• 一台打印机面向多个用户或是程序的情况

经典应用

• 模拟打印机处理多任务
• 模拟道路交通，超市结账排队情况等
• CPU访问
  • 多个进程访问同一个CPU，新进程会被添加到队列，这个队列就是等待CPU使用的进程

部分应用代码实现

约瑟夫/热土豆理论

# 热土豆问题：几个小朋友，围成一圈，用一个热土豆（或别的什么东西），数一个数就抛给下一个人，每数到3，手上有土豆的人就站出来，然后继续，问哪个位置的人最后剩下？

# 利用内置数据类型列表构建队列数据结构
class Queue():
    def __init__(self):
        self._items = []

    def size(self):
        return len(self._items)

    def enqueue(self, data):
        self._items.insert(0, data)

    def dequeue(self):
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

# 热土豆问题逻辑代码
def hot_potato(lists, num):
    q = Queue()
    # 按人名将数据项入队
    for person in lists:
        q.enqueue(person)
    # 直到只剩下一个人，游戏结束
    while q.size() > 1:
        for i in range(num):
            q.enqueue(q.dequeue())
        q.dequeue()
    # 将最后剩下的人返回
    return q.dequeue()

# 模拟热土豆的实例，参数分表代表参加游戏的人名以及土豆每传递几次就出队一个人
last_person = hot_potato(["A", "B", "C", "D", "E", "F", "G", "H", "I", "L", "M", "N", "O"], 3)
print(last_person)

生产者消费者模型

import threading
import queue
 
 
def producer():
    """
    模拟生产者
    :return:
    """
    for i in range(10):
        print("生产包子%s" %i)
        q.put("包子 %s" % i)
 
    print("开始等待所有的包子被取走...")
    q.join()  # 等待这个包子队列被消费完毕
    print("所有的包子被取完了...")
 
 
def consumer(n):
    """
    模拟消费者
    :return:
    """
    while q.qsize() > 0:
        print("%s 取到" % n, q.get())
        q.task_done()  # 每取一个包子，便告知队列这个任务执行完了
 
q = queue.Queue()
 
p = threading.Thread(target=producer,)
p.start()
 
c1 = consumer("xiaochen")