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

堆栈 (Stack)

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

• 压栈 (push): 将元素添加到堆栈顶部。
• 出栈 (pop): 从堆栈顶部移除并返回元素。

堆栈的应用场景包括函数调用、撤销操作、浏览器历史记录、表达式求值、语法分析和深度优先搜索 (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) 的数据结构。 就像排队一样，先进入队列的元素先被处理。

• 入队 (enqueue): 将元素添加到队列尾部。
• 出队 (dequeue): 从队列头部移除并返回元素。

队列的应用场景包括任务调度、广度优先搜索 (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

使用队列实现堆栈:

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

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

以上就是堆栈和队列 ||蟒蛇 ||数据结构和算法的详细内容，更多请关注知识资源分享宝库其它相关文章！