线性表、堆、队列

一、线性表

1.1 定义

  线性表，全名为线性存储结构；其存储方式形象化理解是：将所有数据元素通过一根线串联起来，存储到物理空间中。

1.2 分类

1. 将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）；

2. 将数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）；

1.3 顺序表

顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙；

例如，使用顺序表存储集合 {1,2,3,4,5}，数据最终的存储状态如图 1 所示：

查找元素的时间复杂度是O(1)，增加、删除元素的时间复杂度O(n);
在创建时需要确定长度，实际项目开发过程中很难一开始就确定线性表的大小
需要占用整块连续的内存空间，容易造成存储空间的碎片化

顺序表存储数据使用的其实就是数组

1.4 链表

链表不限制数据的物理存储状态；使用链表存储的数据元素，其物理存储位置是随机的；其实现方式是通过节点（含有指针域与数据域）确定各个数据之间的顺序

1.4.1头节点、头指针和首元节点

一个完整的链表需要以下几部分构成：
头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；

节点：链表中的节点又细分为头节点、首元节点和其他节点：
头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
其他节点：链表中其他的节点；
因此，一个存储 {1,2,3} 的完整链表结构如图 2 所示

链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。

1.4.2 代码实现

# 创建结点类
class ListNode(object):
   def __init__(self, data):
       self.data = data
        self.next = None
 
# 创建链表类
class CreatList(object):
   def __init__(self):
        self.head = ListNode(None)
 
   # 链表初始化函数
   def InitList(self, data):
       # 创建头结点
       self.head = ListNode(data[0])
       p = self.head
       for i in data[1:]:
           node = ListNode(i)
           p.next = node
           p = p.next
 
    # 链表判空
   def IsEmpty(self):
       p = self.head
       if p.next == None:
           print("Empty List!")
           return 1
       else:
           return 0
 
   # 计算链表长度
   def GetLength(self):
       if self.IsEmpty():
           return 0
       p = self.head
       count = 0
       while p:
           count += 1
           p = p.next
       return count
 
   # 遍历链表，输出链表的每个结点值，用“,”隔开
   def ReadList(self):
       if self.IsEmpty():
           return 0
       p = self.head
       while p:
           print(p.data,end = ',')
           p = p.next
       print('')
 
   # 获取链表第i个结点数据
   def GetList(self, i):
       if i > self.GetLength():
           print("第%d个元素不存在", i)
           return 0
       p = self.head
       index = 1
       while index < i:
           p = p.next
           index += 1
       print("第%d个数据为：%d" % (i, p.data))
 
   # 链表插入数据，在第i个结点后插入数据data
   def InsertList(self, i, data):
       if i > self.GetLength():
           print("插入失败！")
           exit(0)
       p = self.head
       index = 1
       while index < i:
           p = p.next
           index += 1
 
       node = ListNode(data)
       node.next = p.next
       p.next = node
 
   # 链表删除函数，删除第i个结点
   def DeleteList(self, i):
       if i > self.GetLength():
           print("删除失败！")
           exit(0)
 
       index = 1
       p = self.head
       while index < i:
           pre = p
           index += 1
           p = p.next
       pre.next = p.next
       p = None
   # 链表逆序
   def reverse(self):
       p = self.head
       q = None
       while p:
           temp = p.next
           p.next = q
           q = p
           p = temp
       self.head = q  
复制代码

1.4.3 总结

1. 链表是动态存储结构，不需要事先分配好存储空间，大小不受限制;

2. 插入、删除的时间复杂度是O(1),查找的时间复杂度是O(n)

二 、 栈

2.1 定义

栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构

栈只能从表的一端存取数据，另一端是封闭的，如图 3 所示；
在栈中，无论是存数据还是取数据，都必须遵循”先进后出”的原则，即最先进栈的元素最后出栈。拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据”先进后出”的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。

2.2 进栈和出栈

基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：
向栈中添加元素，此过程被称为”进栈”（入栈或压栈）；
从栈中提取出指定元素，此过程被称为”出栈”（或弹栈）；

2.3 栈的应用

1. 浏览器实现页面的回退:

  例如，我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A，然后关闭了页面 A 跳转到页面 B，随后又关闭页面 B 跳转到了页面 C。而此时，我们如果想重新回到页面 A，有两个选择：1、重新搜索找到页面 A；2、使用浏览器的”回退”功能。浏览器会先回退到页面 B，而后再回退到页面 A。
浏览器 “回退” 功能的实现，底层使用的就是栈存储结构。当你关闭页面 A 时，浏览器会将页面 A 入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。

1. 检测代码中括号匹配问题：

  多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题。

2.4 栈实现（Python）

#  基于LIFO队列,后进先出(方式一)
import queue
 
q = queue.LifoQueue()
 
for i in range(10):
   q.put(i)
 
while not q.empty():
   print(q.get())
   
#   具有链表性能特征的栈数据结构实现（方式二）  
from collections import deque
 s = deque()
s.append("eat")
s.append("sleep")
s.append("code")
 
print(s)
value = s.pop()
print(value)
复制代码

三、 队列

3.1 定义

队列的两端都”开口”，要求数据只能从一端进，从另一端出；数据的进出要遵循 “先进先出” 的原则。

3.2 队列实现（Python）

Queue是python标准库中的线程安全的队列（FIFO）实现,提供了一个适用于多线程编程的先进先出的数据结构，即队列，用来在生产者和消费者线程之间的信息传递

#  基本FIFO队列
import queue
 
q = queue.Queue()
 
for i in range(10):
    q.put(i)
 
while not q.empty():
    print(q.get())
复制代码