堆栈

其实pyhton的list数据类型就带有堆栈属性，那么我们直接封装成类

class Stack(object):

    __data = []

    def __init__(self):
        pass

    def push(self, data):
        self.__data.append(data)

    def pop(self):
        if self.__data:
            return self.__data.pop()

>>> from data_structure import Stack
>>> a=Stack()
>>> a.push(1)
>>> a.push(2)
>>> a.push(3)
>>> a.pop()
3
>>> a.pop()
2
>>> a.pop()
1
>>> a.pop()

链表

单链表

class SingleLink(object):
   
   def __init__(self, data, next=None):
       self.data = data
       self.next = next

if __name__ == "__main__":
   print("python 数据链表结构基本实现")
   print("构造一个链")
   head = None
   for i in range(5):
       link = SingleLink(i, head)
       head = link

   print("遍历一个链")

   while link:
       print(link.data)
       link = link.next

~/Desktop/desktop » python3 data_structure.py                                                                                tme@localhost
python 数据链表结构基本实现
构造一个链
遍历一个链
4
3
2
1
0

# 根据nums生成一个顺序链表
def make_link(nums):
    head = None
    last_link = None
    for num in nums:
        this_link = SingleLink(num)
        if last_link == None:
            head = this_link
        else:
            last_link.next = this_link
        last_link = this_link
    return head
link = make_link([1,2,4,5,6])
# 遍历链表
while link:
  print(link.data):
  link = link.next

# 删除数据为4的节点
last_link = None
while link:
  if link.data == 4:
    if last_link:
      last_link.next = link.next
  link = link.next
# 在数据2后面插入值为3的节点

树

满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

完全二叉树

去除最后最后一层之后是满二叉树，且叶子节点如果只有一个靠左挂载的树称为完全二叉树。

二叉搜索树

每个节点的左子节点比自己小，右节点不小于自己的树称为二叉搜索树。
二叉搜索树中序遍历出来的结果即是所有数据排序结果

class Tree:
    """搜索二叉树"""
    data = None
    left = None
    right = None

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
      
    def add(self, data):
        if self.data > data:
            if self.left is None:
                self.left = Tree(data)
            else:
                self.left.add(data)
        if self.data <= data:
            if self.right is None:
                self.right = Tree(data)
            else:
                self.right.add(data)
                
    def find(self, data):
        if self.data == data:
            return True
        elif self.data > data:
            if self.left:
                return self.left.find(data)
            else:
                return False
        else:
            if self.right:
                return self.right.find(data)
            else:
                return False

def preorder(tree):
    # 前序遍历
    list_data = []
    def fun(t):
        if t:
            list_data.append(t.data)
            fun(t.left)
            fun(t.right)
    fun(tree)
    return list_data

def inorder(tree):
    # 中序遍历
    list_data = []
    def fun(t):
        if t:
            fun(t.left)
            list_data.append(t.data)
            fun(t.right)
    fun(tree)
    return list_data

def postorder(tree):
    # 后续遍历
    list_data = []
    def fun(t):
        if t:
            fun(t.left)
            fun(t.right)
            list_data.append(t.data)
    fun(tree)
    return list_data

红黑树

在二叉搜索树的情况下，满足一下几点
1、根节点为黑色
2、红色节点不相邻
3、所有路径上的黑色节点都一样多

跳表

图