代码收藏家技术教程 2025-02-24

python 栈和链表

栈（Stack）总结

概念与特性

后进先出（LIFO）：最后入栈的元素最先被移除。

操作受限：所有操作（插入、删除）仅能在栈顶进行。

核心操作

push(element)：将元素压入栈顶。
pop()：移除并返回栈顶元素。
peek()：查看栈顶元素，不修改栈。
isEmpty()：判断栈是否为空。
clear()：清空栈。
size()：返回栈中元素个数。

实现方式

数组实现：需处理栈满（isFull()）和栈空（isEmpty()）的异常。

链表实现：无需固定容量，动态分配内存。

代码示例（数组实现）

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

def push(self, element):
if len(self.items) == self.size:
raise Exception("Stack is full")
self.items.append(element)

def pop(self):
if self.isEmpty():
raise Exception("Stack is empty")
return self.items.pop()

def peek(self):
return self.items[-1] if not self.isEmpty() else None

def isEmpty(self):
return len(self.items) == 0

应用场景

函数调用栈：管理函数调用顺序。

括号匹配：验证表达式语法。

撤销操作：记录操作历史，支持回退。

链表（Linked List）总结

概念与特性

节点结构：每个节点包含数据域和指针域（指向下一个节点）。

非连续存储：物理内存分布灵活，动态分配内存。

单向链表操作

尾部插入：遍历至链表末尾，将新节点链接到末尾节点的 next。
头部插入：将新节点的 next 指向原头节点，更新头指针。
删除节点：遍历至目标节点的前驱，修改指针跳过目标节点。
遍历：从头节点开始，通过 next 指针依次访问所有节点。

代码示例（单向链表）

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

class LinkedList:
def __init__(self):
self.head = Node(None)

def append(self, data):
new_node = Node(data)
current = self.head
while current.next:
current = current.next
current.next = new_node

def prepend(self, data):
new_node = Node(data)
new_node.next = self.head.next
self.head.next = new_node

def remove(self, data):
current = self.head
while current.next and current.next.data != data:
current = current.next
if current.next:
current.next = current.next.next

优缺点对比

优点	缺点
动态内存分配，高效利用内存	无法随机访问，需顺序遍历
插入/删除时间复杂度 O(1)（头部）	指针操作复杂，易出错