Python栈的时间复杂度分析

2023-04-10 00:00:00 分析时间复杂度

Python栈的常见操作包括进栈（push）、出栈（pop）和获取栈顶元素（top）。下面分别分析这些操作的时间复杂度。
1. 进栈（push）
向栈中添加一个元素，时间复杂度为O(1)，因为只需要在栈顶添加就可以了，不需要移动其他元素。
代码演示：

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)

出栈（pop）
从栈中删除一个元素并返回它，时间复杂度也为O(1)，因为只需要弹出栈顶元素即可。
代码演示：

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()

获取栈顶元素（top）
返回栈顶元素，时间复杂度为O(1)，因为直接返回栈顶元素即可。
代码演示：

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def top(self):
        return self.items[-1]

综上，Python栈的常见操作时间复杂度均为O(1)，因为它们都只需要操作栈顶元素，并且不需要移动其他元素。

相关文章