本文共 5384 字，大约阅读时间需要 17 分钟。

#51 队列的实现

Queue 类用于实现固定长度的队列，队列在满的时候空一个位置。构造方法中接受大小参数，默认为100，表示队列最大容纳的元素个数。

代码示例：

class Queue:    def __init__(self, size=100):        self.size = size        self.queue = [0] * size        self.rear = 0  # 队尾指针        self.front = 0  # 队首指针    def push(self, element):        if not self.is_filled():            self.rear = (self.rear + 1) % self.size            self.queue[self.rear] = element        else:            raise IndexError("Queue is filled.")    def pop(self):        if not self.is_empty():            self.front = (self.front + 1) % self.size            return self.queue[self.front]        else:            raise IndexError("Queue is empty.")    def is_empty(self):        return self.rear == self.front    def is_filled(self):        return (self.rear + 1) % self.size == self.front# 创建一个大小为5的队列q = Queue(5)# 将前4个元素逐个推入队列（队满时空一个位置）for i in range(4):    q.push(i)# 输出队列是否已满print(q.is_filled())  # 结果为True# 取出队列第一个元素print(q.pop())  # 结果为0# 推入第5个元素（4）q.push(4)

#52 队列的内置模块

Python standard library 中提供了 collections.deque 模块，用于实现双向队列。双向队列可以在队列的两端进行元素的插入和删除操作，适用于需要同时处理输入和输出的场景。

使用示例：

from collections import dequeq = deque([1, 2, 3, 4, 5], 5)# 队尾添加元素q.append(6)# 队首移除元素q.popleft()# 队尾添加元素q.appendleft(1)  # 队首为1# 队尾移除元素q.pop()# 示例函数用于读取文件的最后N行def tail(n):    with open('test.txt', 'r', encoding='utf-8') as f:        q = deque(f, n)        return q# 读取并打印文件的最后5行for line in tail(5):    print(line, end='')

注意事项：

• deque 是双端队列，支持 O(1) 时间的 appendleft 和 popleft 操作。
• 使用 deque 读取文件时，可以通过指定最大长度来控制读取的行数，确保不会读取超出文件行数。

#53 栈和队列的应用：迷宫问题

迷宫问题可以通过栈（深度优先搜索）或队列（广度优先搜索）来解决。以下使用栈来回溯迷宫路径。

代码示例：

def maze_path(x1, y1, x2, y2):    stack = []    stack.append((x1, y1))    directions = [        lambda x, y: (x + 1, y),        lambda x, y: (x - 1, y),        lambda x, y: (x, y - 1),        lambda x, y: (x, y + 1)    ]    maze = [        [1,1,1,1,1,1,1,1,1,1],        [1,0,0,1,0,0,0,1,0,1],        [1,0,0,1,0,0,0,1,0,1],        [1,0,0,0,0,1,1,0,0,1],        [1,0,1,1,1,0,0,0,0,1],        [1,0,0,0,1,0,0,0,0,1],        [1,0,1,0,0,0,1,0,0,1],        [1,0,1,1,1,0,1,1,0,1],        [1,1,0,0,0,0,0,0,0,1],        [1,1,1,1,1,1,1,1,1,1]    ]    while stack:        current = stack[-1]        if current[0] == x2 and current[1] == y2:            for node in stack:                print(node)            return True        for direction in directions:            next_node = direction(current[0], current[1])            if 0 <= next_node[0] < 10 and 0 <= next_node[1] < 10 and maze[next_node[0]][next_node[1]] == 0:                stack.append(next_node)                maze[next_node[0]][next_node[1]] = 2                break            else:                maze[current[0]][current[1]] = 2                stack.pop()    print("没有路")    return Falsemaze_path(1, 1, 8, 8)

#54 使用队列进行迷宫问题：实现

可以使用队列配合哈希表来实现广度优先搜索迷宫路径寻找。

代码示例：

from collections import dequedef maze_path_queue(x1, y1, x2, y2):    queue = deque()    queue.append((x1, y1, -1))    path = []    directions = [        (1, 0),        (-1, 0),        (0, -1),        (0, 1)    ]    while queue:        current = queue.popleft()        path.append(current)        x, y = current[0], current[1]        if x == x2 and y == y2:            print("找到了路径：")            for node in path:                print(node)            return True        for dx, dy in directions:            nx = x + dx            ny = y + dy            if 0 <= nx < 10 and 0 <= ny < 10 and maze[nx][ny] == 0:                new_node = (nx, ny, len(path) - 1)                queue.append(new_node)                maze[nx][ny] = 2    print("没有路")    return Falsemaze_path_queue(1, 1, 8, 8)

#57 链表介绍

链表是一种线性数据结构，由节点组成，每个节点包含数据域和指向下一个节点的指针。链表的优点是插入和删除操作的时间复杂度较低，而缺点是随机访问的时间复杂度较高。

节点类定义：

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

链表创建示例：

class Node:    def __init__(self, item):        self.item = item        self.next = Nonedef create_linked_list_head(li):    if not li:        return None    head = Node(li[0])    for element in li[1:]:        node = Node(element)        node.next = head        head = node    return headlk = create_linked_list_head([1, 2, 3])print(lk.item)  # 输出3print(lk.next.item)  # 输出2print(lk.next.next.item)  # 输出1print(lk.next.next.next.item)  # 报错：没有该属性

#59 链表的插入和删除

链表的插入和删除操作通常采用头插法或尾插法。这些操作不需要移动数据，仅通过指针赋值即可完成，时间复杂度为O(1)。

插入示例：

def insert_after_head(p, new_node):    p.next = new_node    new_node.prior = pdef insert_after_tail(t, new_node):    t.next = new_node    new_node.prior = tdef delete_node_by_prior(prior):    p = prior    p_next = p.next    if p_next:        p_next.prior = prior    del p# 创建链表测试a = Node(1)a.next = Node(2)a.next.next = Node(3)insert_after_head(a.next, Node(4))print(a.next.next.item)  # 输出4delete_node_by_prior(a.next.prior)print(a.next.item)  # still 2

#60 双链表

双链表每个节点包含前驱和后驱指针，支持双向遍历。双链表的插入和删除操作比较灵活。

节点类定义：

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

双链表插入示例：

def insert_after(tail, new_node):    new_node.next = tail.next    new_node.prior = tail    tail.next = new_node    tail = new_nodedef delete_node(node):    if node.prior:        node.prior.next = node.next    if node.next:        node.next.prior = node.prior    if node.prior is None and node.next is None:        head = node    del node

常用操作总结：

• 插入操作：O(1) 时间。
• 删除操作：O(1) 时间。
• Random access：O(n) 时间。

以上内容主要介绍了队列、链表及其应用案例，涵盖了基础理论和实际应用示例。

转载地址：http://ictuk.baihongyu.com/