Python实现包含min函数的栈

以下是“Python实现包含min函数的栈”的完整攻略：

一、问题描述

设计一个支持push、pop、top和min操作的栈。其中，min操作返回栈中最小的元素。要求所有操作的时间复杂度都为O(1)。

二、解决方案

2.1 栈的基本操作

栈是一种后进先出（LIFO）的数据结构，支持以下基本操作：

• push(x)：将元素x压入栈中。
• pop()：弹出栈顶元素。
• top()：返回栈顶元素。
• isEmpty()：判断栈是否为空。

在Python中，我们可以使用列表来实现栈。以下是一个示例，演示了如何使用列表实现栈的基本操作：

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

    def pop(self):
        return self.stack.pop()

    def top(self):
        return self.stack[-1]

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

在这个示例中，我们定义了一个名为Stack的类，它包含了push、pop、top和isEmpty等基本操作。我们使用列表self.stack来存储栈中的元素。在push操作中，我们使用列表的append()函数将元素x压入栈中。在pop操作中，我们使用列表的pop()函数弹出栈顶元素。在top操作中，我们使用列表的索引-1来返回栈顶元素。在isEmpty操作中，我们使用列表的长度来判断栈是否为空。

2.2 包含min函数的栈

为了实现包含min函数的栈，我们需要在栈中维护一个辅助栈，用于存储当前栈中的最小元素。每次push操作时，我们将元素x压入栈中，并将x与辅助栈的栈顶元素进行比较，如果x小于等于栈顶元素，则将x也压入辅助栈中。每次pop操作时，我们弹出栈顶元素，并将其与辅助栈的栈顶元素进行比较，如果相等，则也弹出辅助栈的栈顶元素。最后，我们可以使用辅助栈的栈顶元素来实现min函数。以下是一个示例，演示了如何实现包含min函数的栈：

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        x = self.stack.pop()
        if x == self.min_stack[-1]:
            self.min_stack.pop()
        return x

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

在这个示例中，我们定义了一个名为MinStack的类，它包含了push、pop、top和getMin等操作。我们使用两个列表self.stack和self.min_stack来分别存储栈中的元素和最小元素。在push操作中，我们首先将元素x压入栈中，然后将x与辅助栈的栈顶元素进行比较，如果x小于等于栈顶元素，则将x也压入辅助栈中。在pop操作中，我们弹出栈顶元素，并将其与辅助栈的栈顶元素进行比较，如果相等，则也弹出辅助栈的栈顶元素。在getMin操作中，我们返回辅助栈的栈顶元素。

三、示例说明

以下是两个示例，演示了如何使用Python实现包含min函数的栈：

3.1 示例1

stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)
print(stack.getMin())  # 输出 -3
stack.pop()
print(stack.top())     # 输出 0
print(stack.getMin())  # 输出 -2

在这个示例中，我们首先创建了一个MinStack对象stack，并使用push操作将-2、0和-3压入栈中。然后，我们使用getMin操作来获取栈中的最小元素，输出结果为-3。接着，我们使用pop操作弹出栈顶元素-3，并使用top操作获取栈顶元素0。最后，我们再次使用getMin操作来获取栈中的最小元素，输出结果为-2。

3.2 示例2

stack = MinStack()
stack.push(2)
stack.push(0)
stack.push(3)
stack.push(0)
print(stack.getMin())  # 输出 0
stack.pop()
print(stack.getMin())  # 输出 0
stack.pop()
print(stack.getMin())  # 输出 0
stack.pop()
print(stack.getMin())  # 输出 2

在这个示例中，我们首先创建了一个MinStack对象stack，并使用push操作将2、0、3和0压入栈中。然后，我们使用getMin操作来获取栈中的最小元素，输出结果为0。接着，我们使用pop操作弹出栈顶元素0，并再次使用getMin操作来获取栈中的最小元素，输出结果为0。我们重复这个过程，直到栈为空。最后，我们再次使用getMin操作来获取栈中的最小元素，输出结果为2。

以上就是“Python实现包含min函数的栈”的完整攻略，包括问题描述解决方案和两个示例说明。