刷题-DAY9

**刷题 DAY9**

今天我们将继续我们的刷题之旅，主题是数据结构与算法。我们将讨论一些常见的数据结构和算法，并提供相关的代码示例。

### 一、栈和队列栈和队列都是线性数据结构，它们遵循先进先出（FIFO）或后进先出（LIFO）的原则。

####1. 栈栈是一种后进先出的数据结构，新元素总是被压入到栈顶，而老元素总是从栈顶弹出。我们可以使用数组或链表来实现栈。

class Stack:
 def __init__(self):
 self.items = []

 def push(self, item):
 """添加元素"""
 self.items.append(item)

 def pop(self):
 """移除元素"""
 return self.items.pop()

 def peek(self):
 """查看顶部元素"""
 if not self.is_empty():
 return self.items[-1]
 else:
 raise IndexError("Stack is empty")

 def is_empty(self):
 """检查是否为空"""
 return len(self.items) ==0

####2. 队列队列是一种先进先出的数据结构，新元素总是被添加到队尾，而老元素总是从队头移除。我们可以使用数组或链表来实现队列。

class Queue:
 def __init__(self):
 self.items = []

 def enqueue(self, item):
 """添加元素"""
 self.items.append(item)

 def dequeue(self):
 """移除元素"""
 return self.items.pop(0)

 def peek(self):
 """查看头部元素"""
 if not self.is_empty():
 return self.items[0]
 else:
 raise IndexError("Queue is empty")

 def is_empty(self):
 """检查是否为空"""
 return len(self.items) ==0

### 二、链表链表是一种线性数据结构，它的元素通过指针连接起来。

####1. 单向链表单向链表是最基本的链表类型，每个结点包含一个值和一个指向下一个结点的指针。

class Node:
 def __init__(self, value):
 self.value = value self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def append(self, value):
 """添加元素"""
 node = Node(value)
 if not self.head:
 self.head = node else:
 current = self.head while current.next:
 current = current.next current.next = node def traverse(self):
 """遍历链表"""
 current = self.head while current:
 print(current.value)
 current = current.next

####2. 双向链表双向链表是链表的一种变体，每个结点包含一个值和两个指针，分别指向前一个结点和后一个结点。

class Node:
 def __init__(self, value):
 self.value = value self.prev = None self.next = Noneclass DoublyLinkedList:
 def __init__(self):
 self.head = None self.tail = None def append(self, value):
 """添加元素"""
 node = Node(value)
 if not self.head:
 self.head = node self.tail = node else:
 current = self.head while current.next:
 current = current.next current.next = node node.prev = current def traverse(self):
 """遍历链表"""
 current = self.head while current:
 print(current.value)
 current = current.next

### 三、树和图树是一种非线性数据结构，它的元素通过父子关系连接起来。图是一种更复杂的非线性数据结构，它的元素通过任意关系连接起来。

####1. 二叉树二叉树是最基本的树类型，每个结点最多有两个孩子，分别称为左孩子和右孩子。

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Noneclass BinaryTree:
 def __init__(self):
 self.root = None def insert(self, value):
 """添加元素"""
 node = Node(value)
 if not self.root:
 self.root = node else:
 current = self.root while True:
 if value < current.value:
 if not current.left:
 current.left = node break current = current.left else:
 if not current.right:
 current.right = node break current = current.right def traverse(self):
 """遍历树"""
 self._traverse(self.root)

 def _traverse(self, node):
 if node:
 print(node.value)
 self._traverse(node.left)
 self._traverse(node.right)

####2. 图图是一种更复杂的非线性数据结构，它的元素通过任意关系连接起来。

class Node:
 def __init__(self, value):
 self.value = value self.neighbors = []

class Graph:
 def __init__(self):
 self.nodes = {}

 def add_node(self, value):
 """添加结点"""
 node = Node(value)
 self.nodes[value] = node def add_edge(self, from_value, to_value):
 """添加边"""
 if from_value not in self.nodes:
 self.add_node(from_value)
 if to_value not in self.nodes:
 self.add_node(to_value)
 self.nodes[from_value].neighbors.append(self.nodes[to_value])

 def traverse(self):
 """遍历图"""
 for node in self.nodes.values():
 print(node.value)
 for neighbor in node.neighbors:
 print(neighbor.value)

以上就是今天的刷题内容。我们讨论了栈、队列、链表、树和图等数据结构和算法，并提供了相关的代码示例。希望这些内容能够帮助你更好地理解这些概念。