优缺点

使用场景

数组

数组是一种线性数据结构，用于存储同一类型的一组数据。它的元素在内存中存储是连续的，可以通过索引快速访问元素，适合随机访问。

下面是一个包含5个元素的整型数组的内存结构示意图：

  Index      0        1      2       3        4
  -----------------------------------------------------
  Element |  10   |  -2   |  3    |  0    |  8    |
  -----------------------------------------------------

链表

链表也是一种线性数据结构，用指针将一组数据按序连接起来，每个节点包含一个数据和一个指向下一个节点的指针。

     +--------+      +--------+      +--------+
head | value  | next | value  | next | value  | None
     +--------+      +--------+      +--------+
        |               |               |
        V               V               V
     +--------+      +--------+      +--------+
     | node 1 |----> | node 2 |----> | node 3 |
     +--------+      +--------+      +--------+

在上面的图中，链表由一个个节点组成，每个节点包含两个部分，一个是 value 表示节点存储的数据，另一个是 next 表示下一个节点的指针。链表的主体是由一个 head 指针指向链表的第一个节点，而最后一个节点的 next 则指向空地址 None。

栈

栈是一种先进后出的数据结构。

基本操作

• push：将元素压入栈顶
• pop：将栈顶元素弹出
• top：获取栈顶元素但不弹出
• isEmpty：判断栈是否为空
• size：获取栈的元素个数

基于数组

class ArrayStack:
    def __init__(self, capacity):
        self._capacity = capacity
        self._data = [None] * self._capacity
        self._size = 0

    def push(self, val):
        if self._size == self._capacity:
            self._expand_capacity()
        self._data[self._size] = val
        self._size += 1

    def _expand_capacity(self):
        self._capacity *= 2
        new_data = [None] * self._capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data

    def pop(self):
        if self.is_empty():
            raise Exception("stack is empty")
        self._size -= 1
        return self._data[self._size]

    def is_empty(self):
        return self._size == 0

    def top(self):
        if self.is_empty():
            raise Exception("stack is empty")
        return self._data[self._size - 1]

    def size(self):
        return self._size

基于链表

class StackNode:
    def __init__(self, val):
        self.val = val
        self.next = None


class ChainStack:
    def __init__(self):
        self._top_node = None
        self._size = 0

    def push(self, val):
        new_node = StackNode(val)
        new_node.next = self._top_node
        self._top_node = new_node
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise Exception("stack is empty")
        val = self._top_node.val
        self._top_node = self._top_node.next
        self._size -= 1
        return val

    def is_empty(self):
        return self._top_node is None

    def top(self):
        if self.is_empty():
            raise Exception("stack is empty")
        return self._top_node.val

    def size(self):
        return self._size

队列

队列是一种先进先出的数据结构，类似于排队。

基本操作

• 入队（enqueue）：向队列尾部添加一个新元素。
• 出队（dequeue）：从队列头部删除一个元素。
• 获取队列头部元素（peek）：查看队列头部的元素，但不将其删除。
• 判断队列是否为空（isEmpty）：检查队列是否为空，即队列中是否有元素。
• 获取队列中元素的数量（size）：获取队列中元素的数量。

基于数组

class ArrayQueue:
    def __init__(self, capacity):
        self._capacity = capacity
        self._data = [None] * capacity
        self._head = self._tail = self._size = 0

    def enqueue(self, val):
        if self._size == self._capacity:
            return False
        self._data[self._tail] = val
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return None
        val = self._data[self._head]
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return val

    def is_empty(self):
        return self._size == 0

    def size(self):
        return self._size

基于链表

class QueueNode:
    def __init__(self, val):
        self.val = val
        self.next = None


class ChainQueue:
    def __init__(self, capacity):
        self._capacity = capacity
        self._head = self._tail = None
        self._size = 0

    def enqueue(self, val):
        if self._size == self._capacity:
            return False
        node = QueueNode(val)
        if self.is_empty():
            self._head = self._tail = node
        else:
            self._tail.next = node
            self._tail = self._tail.next
        self._size += 1
        return True

    def is_empty(self):
        return self._size == 0

    def dequeue(self):
        if self.is_empty():
            return None
        val = self._head.val
        self._head = self._head.next
        self._size -= 1
        return val

    def size(self):
        return self._size

树

名词概念

特性

• 一棵非空的树有且只有一个根节点。
• 每个节点有零个或多个子节点。
• 每个非根节点有且仅有一个父节点。
• 如果节点A是节点B的子节点，则B是A的父节点。
• 如果一棵树的每个节点都不超过n个子节点，则该树称为n叉树。

常用特殊的树