做任务什么网站,网站建设价格请咨询兴田德润,动漫制作公司排名,多语言多商户商城源码一、计算机领域的地位 在计算机科学的广袤领域中#xff0c;数据结构犹如一座精巧的大厦#xff0c;为信息的存储和处理提供了坚实的框架。而在众多的数据结构中#xff0c;栈和队列宛如两颗璀璨的明珠#xff0c;各自闪耀着独特的光芒。 栈和队列虽然看似简单数据结构犹如一座精巧的大厦为信息的存储和处理提供了坚实的框架。而在众多的数据结构中栈和队列宛如两颗璀璨的明珠各自闪耀着独特的光芒。 栈和队列虽然看似简单却蕴含着深刻的逻辑和强大的功能。它们是解决众多复杂问题的基石从程序的执行流程控制到各种算法的优化从操作系统的任务调度到网络通信中的数据传输栈和队列都发挥着不可或缺的作用。 深入理解栈和队列不仅能够提升我们对数据组织和操作的认知更能为我们在编程和算法设计中打开新的思路使我们能够更加高效、优雅地解决实际问题。在接下来的篇章中让我们一同走进栈和队列的精彩世界探索它们的奥秘与魅力。 二、栈Stack的详解
栈是一种特殊的线性表其操作遵循“后进先出Last In First OutLIFO”的原则。
一、栈的定义 栈只允许在一端进行插入入栈和删除出栈操作这一端被称为栈顶而另一端则被称为栈底。
二、栈的基本操作 入栈Push将元素添加到栈顶。 例如一个初始为空的栈依次入栈元素 10、20、30 此时栈顶元素为 30 。 出栈Pop删除栈顶元素。 对于上述栈执行出栈操作先弹出的是 30 。 读取栈顶元素Peek获取栈顶元素的值但不删除它。 判空IsEmpty判断栈是否为空。
三、栈的实现方式 顺序栈使用数组来实现。
优点操作简单随机访问速度快。缺点需要预先分配固定大小的空间可能造成空间浪费或溢出。
下面是用python实现的顺序栈结构
# 顺序栈实现
class SequentialStack:def __init__(self, size10):初始化顺序栈参数:size (int): 栈的初始大小self.stack [None] * size # 存储栈元素的列表self.top -1 # 栈顶指针def is_empty(self):判断栈是否为空返回:bool: 如果栈为空返回 True否则返回 Falsereturn self.top -1def is_full(self):判断栈是否已满返回:bool: 如果栈已满返回 True否则返回 Falsereturn self.top len(self.stack) - 1def push(self, element):向栈中压入元素参数:element: 要压入栈的元素异常:Exception: 如果栈已满抛出Stack Overflow异常if self.is_full():raise Exception(Stack Overflow)self.top 1self.stack[self.top] elementdef pop(self):从栈中弹出元素返回:弹出的元素异常:Exception: 如果栈为空抛出Stack Underflow异常if self.is_empty():raise Exception(Stack Underflow)element self.stack[self.top]self.stack[self.top] Noneself.top - 1return elementdef peek(self):查看栈顶元素但不弹出返回:栈顶元素异常:Exception: 如果栈为空抛出Stack is empty异常if self.is_empty():raise Exception(Stack is empty)return self.stack[self.top]2. 链式栈使用链表来实现。
优点灵活不受固定空间限制。缺点访问节点需要遍历效率相对较低。
下面是用python实现的链式栈结构
# 链式栈节点
class Node:def __init__(self, dataNone):初始化链式栈节点参数:data: 节点存储的数据默认为 Noneself.data dataself.next None# 链式栈实现
class LinkedStack:def __init__(self):初始化链式栈self.top None # 栈顶节点def is_empty(self):判断链式栈是否为空返回:bool: 如果为空返回 True否则返回 Falsereturn self.top is Nonedef push(self, element):向链式栈中压入元素参数:element: 要压入的元素new_node Node(element) # 创建新节点new_node.next self.top # 新节点指向当前栈顶self.top new_node # 更新栈顶def pop(self):从链式栈中弹出元素返回:弹出的元素异常:Exception: 如果栈为空抛出Stack Underflow异常if self.is_empty():raise Exception(Stack Underflow)element self.top.data # 获取栈顶节点数据self.top self.top.next # 更新栈顶return elementdef peek(self):查看链式栈栈顶元素但不弹出返回:栈顶元素异常:Exception: 如果栈为空抛出Stack is empty异常if self.is_empty():raise Exception(Stack is empty)return self.top.data
四、栈的应用场景 函数调用函数的调用和返回可以通过栈来管理。
当一个函数被调用时相关的参数、局部变量等信息被压入栈中函数返回时这些信息从栈中弹出。 表达式求值如中缀表达式转后缀表达式然后进行计算。 括号匹配检查表达式中的括号是否正确匹配。 回溯算法在搜索过程中保存当前状态以便回溯。 总之栈虽然结构简单但在计算机科学的众多领域中发挥着重要作用是理解和解决许多复杂问题的基础工具。 三、队列(Queue)的详解
一、队列的定义 队列只允许在一端进行插入操作称为队尾Rear在另一端进行删除操作称为队头Front。
二、队列的基本操作 入队Enqueue将元素添加到队尾。 例如一个初始为空的队列依次入队元素 5、15、25 此时队头元素为 5 。 出队Dequeue删除队头元素。 对于上述队列执行出队操作先弹出的是 5 。 读取队头元素Front获取队头元素的值但不删除它。 判空IsEmpty判断队列是否为空。 判满IsFull对于有固定大小的队列判断是否已满。
三、队列的实现方式 顺序队列使用数组来实现。 可能会出现“假溢出”的情况即队列未满但无法再插入元素。为解决此问题可采用循环队列的方式。
以下是用python代码实现的顺序队列
class SequentialQueue:def __init__(self, size10):self.queue [None] * sizeself.front 0self.rear 0def is_empty(self):return self.front self.reardef is_full(self):return (self.rear 1) % len(self.queue) self.frontdef enqueue(self, element):if self.is_full():raise Exception(Queue Overflow)self.queue[self.rear] elementself.rear (self.rear 1) % len(self.queue)def dequeue(self):if self.is_empty():raise Exception(Queue Underflow)element self.queue[self.front]self.queue[self.front] Noneself.front (self.front 1) % len(self.queue)return elementdef get_front(self):if self.is_empty():raise Exception(Queue is empty)return self.queue[self.front] 创建一个队列对象即可使用。 链式队列使用链表来实现。
以下是用python实现的链式队列
class Node:def __init__(self, dataNone):self.data dataself.next Noneclass Queue:def __init__(self):self.front Noneself.rear Nonedef enqueue(self, data):new_node Node(data)if not self.rear:self.front new_nodeself.rear new_nodeelse:self.rear.next new_nodeself.rear new_nodedef dequeue(self):if not self.front:return Queue is emptytemp self.frontif self.front self.rear:self.front Noneself.rear Noneelse:self.front self.front.nextreturn temp.datadef is_empty(self):return self.front is Nonedef print_queue(self):current self.frontwhile current:print(current.data, end )current current.nextprint()# 测试队列
q Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.print_queue()
print(q.dequeue())
q.print_queue()
经测试得出链式队列具有较强的稳定性。
四、队列的应用场景 任务调度操作系统按照任务进入队列的先后顺序进行调度。 消息队列在分布式系统中用于消息的传递和处理。 广度优先搜索在图的遍历中使用队列来保存待访问的节点。 总之队列以其独特的先进先出特性在计算机科学和实际应用中发挥着重要作用为数据的有序处理提供了有效的手段。 四、BFS广度优先搜索和队列的关系 BFS 通常使用队列来实现。在 BFS 中我们先访问起始节点然后将其相邻节点放入队列。接着依次取出队列头部的节点并将其未访问过的相邻节点放入队列。这个过程一直持续直到队列为空。
例如对于一个简单的二叉树
class TreeNode:def __init__(self, value):self.value valueself.left Noneself.right None# 构建二叉树
root TreeNode(1)
root.left TreeNode(2)
root.right TreeNode(3)
root.left.left TreeNode(4)
root.left.right TreeNode(5)def bfs(root):queue [root]while queue:current queue.pop(0)print(current.value)if current.left:queue.append(current.left)if current.right:queue.append(current.right)bfs(root)
五、DFS深度优先搜索和栈的关系 DFS 通常使用栈来实现。在 DFS 中我们先访问起始节点然后将其相邻节点压入栈。接着取出栈顶节点并将其未访问过的相邻节点压入栈。这个过程一直持续直到栈为空。
以下是一个使用栈实现 DFS 的示例
def dfs(root):stack [root]while stack:current stack.pop()print(current.value)if current.right:stack.append(current.right)if current.left:stack.append(current.left)dfs(root)
总结 队列是先进先出的数据结构适合 BFS 逐层扩展搜索。栈是先进后出的数据结构适合 DFS 深入一条路径后再回溯。通过这些数据结构的特性能够有效地实现不同的搜索策略。 例如在图的遍历中如果要尽快找到距离起始节点较近的所有节点通常使用 BFS而如果要探索整个图的所有可能路径或者找到一条到达目标节点的最长路径可能会使用 DFS。 “且将新火试新茶诗酒趁年华”——《望江南·超然台作》
