堆栈和队列 ||蟒蛇 ||数据结构和算法

百变鹏仔 2个月前 (01-14) #Python

文章标签堆栈

堆栈 (Stack)

堆栈是一种后进先出 (LIFO) 的数据结构。想象一下一叠盘子：你只能从顶部添加或移除盘子。

堆栈的应用场景包括函数调用、撤销操作、浏览器历史记录、表达式求值、语法分析和深度优先搜索 (DFS) 等。

使用数组实现堆栈:

以下 Python 代码演示了使用数组实现堆栈：

class Stack:    def __init__(self):        self.items = []    def is_empty(self):        return len(self.items) == 0    def push(self, item):        self.items.append(item)    def pop(self):        if not self.is_empty():            return self.items.pop()        return None    def peek(self):        if not self.is_empty():            return self.items[-1]        return None

队列 (Queue)

队列是一种先进先出 (FIFO) 的数据结构。就像排队一样，先进入队列的元素先被处理。

队列的应用场景包括任务调度、广度优先搜索 (BFS)、打印队列、网络路由、呼叫中心、流媒体和事件处理等。

使用数组实现队列:

以下 Python 代码演示了使用数组实现队列：

class Queue:    def __init__(self):        self.items = []    def is_empty(self):        return len(self.items) == 0    def enqueue(self, item):        self.items.append(item)    def dequeue(self):        if not self.is_empty():            return self.items.pop(0)        return None    def peek(self):        if not self.is_empty():            return self.items[0]        return None

使用堆栈实现队列:

可以使用两个堆栈来模拟队列的行为。

class QueueUsingStacks:    def __init__(self):        self.stack1 = []        self.stack2 = []    def enqueue(self, item):        self.stack1.append(item)    def dequeue(self):        if not self.stack2:            while self.stack1:                self.stack2.append(self.stack1.pop())        if self.stack2:            return self.stack2.pop()        return None    def peek(self):        if not self.stack2:            while self.stack1:                self.stack2.append(self.stack1.pop())        if self.stack2:            return self.stack2[-1]        return None    def is_empty(self):        return not self.stack1 and not self.stack2

使用队列实现堆栈:

同样，可以使用两个队列来模拟堆栈的行为。（代码略，原理与上面类似，只是入队和出队的操作顺序不同）

这些代码示例提供了堆栈和队列的基本实现，以及如何使用它们来模拟彼此的功能。实际应用中可能需要考虑更高级的特性，例如容量限制和异常处理。

文章推荐

堆栈和队列 ||蟒蛇 ||数据结构和算法

Python实现字典的key和values的交换

使用Python脚本来获取Cisco设备信息的示例

Python的Django中django-userena组件的简单使用教程

零基础写python爬虫之神器正则表达式

零基础写python爬虫之抓取百度贴吧代码分享