使用Python实现数据结构的10个函数

数据结构是指在计算机中存储、组织和管理数据的方式，Python是一种广泛应用于科学计算、数据分析和人工智能的编程语言，具有易学易用、高效灵活和丰富的数据结构支持等特点，因此，在Python中实现数据结构是非常方便的。

下面介绍使用Python实现数据结构的10个函数。

1. Stack（栈）

栈是一种先进后出（LIFO）的数据结构，可以使用Python内置的列表实现。实现方法如下：

class Stack:
    def __init__(self):
        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[-1]
    
    def size(self):
        return len(self.items)

2. Queue（队列）

队列是一种先进先出（FIFO）的数据结构，可以使用Python内置的deque实现。实现方法如下：

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        return self.items.popleft()
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

3. Linked List（链表）

链表是一种节点之间通过指针相互连接构成的数据结构，可以使用Python实现。实现方法如下：

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    def add_first(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def add_last(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            last_node = self.head
            while last_node.next:
                last_node = last_node.next
            last_node.next = new_node
    
    def insert_after(self, prev_node, data):
        if not prev_node:
            print("Previous node is not in the Linked List")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node
    
    def delete_node(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        cur_node = self.head
        while cur_node.next:
            if cur_node.next.data == data:
                cur_node.next = cur_node.next.next
                return
            cur_node = cur_node.next
    
    def print_list(self):
        cur_node = self.head
        while cur_node:
            print(cur_node.data)
            cur_node = cur_node.next

4. Doubly Linked List（双向链表）

双向链表比单向链表多了一个指针，即指向前一个节点的指针，可以使用Python实现。实现方法如下：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
    
    def add_first(self, data):
        new_node = Node(data)
        new_node.next = self.head
        if self.head:
            self.head.prev = new_node
        self.head = new_node
    
    def add_last(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            last_node = self.head
            while last_node.next:
                last_node = last_node.next
            last_node.next = new_node
            new_node.prev = last_node
    
    def insert_after(self, prev_node, data):
        if not prev_node:
            print("Previous node is not in the Linked List")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        new_node.prev = prev_node
        prev_node.next = new_node
        if new_node.next:
            new_node.next.prev = new_node
    
    def delete_node(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            self.head.prev = None
            return
        cur_node = self.head
        while cur_node.next:
            if cur_node.next.data == data:
                cur_node.next = cur_node.next.next
                if cur_node.next:
                    cur_node.next.prev = cur_node
                return
            cur_node = cur_node.next
    
    def print_list(self):
        cur_node = self.head
        while cur_node:
            print(cur_node.data)
            cur_node = cur_node.next

5. Binary Tree（二叉树）

二叉树是一种每个节点最多只有两个子节点的树形结构，可以使用Python实现。实现方法如下：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, val):
        self.root = Node(val)
    
    def insert(self, val):
        node = Node(val)
        if not self.root:
            self.root = node
        else:
            q = [self.root]
            while q:
                n = q.pop(0)
                if not n.left:
                    n.left = node
                    return
                elif not n.right:
                    n.right = node
                    return
                else:
                    q.append(n.left)
                    q.append(n.right)
    
    def inorder_traversal(self, node):
        if not node:
            return
        self.inorder_traversal(node.left)
        print(node.val)
        self.inorder_traversal(node.right)
    
    def preorder_traversal(self, node):
        if not node:
            return
        print(node.val)
        self.preorder_traversal(node.left)
        self.preorder_traversal(node.right)
    
    def postorder_traversal(self, node):
        if not node:
            return
        self.postorder_traversal(node.left)
        self.postorder_traversal(node.right)
        print(node.val)

6. Binary Search Tree（二叉搜索树）

二叉搜索树是一种每个节点最多只有两个子节点且左子节点小于右子节点的树形结构，可以使用Python实现。实现方法如下：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        node = Node(val)
        if not self.root:
            self.root = node
        else:
            cur_node = self.root
            while True:
                if val < cur_node.val:
                    if not cur_node.left:
                        cur_node.left = node
                        return
                    cur_node = cur_node.left
                else:
                    if not cur_node.right:
                        cur_node.right = node
                        return
                    cur_node = cur_node.right
    
    def search(self, val):
        cur_node = self.root
        while cur_node and cur_node.val != val:
            if val < cur_node.val:
                cur_node = cur_node.left
            else:
                cur_node = cur_node.right
        return cur_node != None
    
    def inorder_traversal(self, node):
        if not node:
            return
        self.inorder_traversal(node.left)
        print(node.val)
        self.inorder_traversal(node.right)
    
    def preorder_traversal(self, node):
        if not node:
            return
        print(node.val)
        self.preorder_traversal(node.left)
        self.preorder_traversal(node.right)
    
    def postorder_traversal(self, node):
        if not node:
            return
        self.postorder_traversal(node.left)
        self.postorder_traversal(node.right)
        print(node.val)

7. Heap（堆）

堆是一种可以快速找出最大/最小元素的数据结构，可以使用Python的heapq模块实现。实现方法如下：

`python

import heapq

class Heap:

def __init__(self, heap=[]):

self.heap = heap

heapq.heapify(self.heap)

def push(self, val):

heapq.heappush(self.heap, val)

def pop(self):

return heapq.heappop(self.heap)

def is_empty(self):

return len(self.heap) == 0

def size(self):

return len(self.heap)

def peek