如何使用数组实现一个栈？

推荐答案

// www.javascriptcn.com code example
class Stack:
    def __init__(self):
        self.stack = []

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

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.stack.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.stack[-1]

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

    def size(self):
        return len(self.stack)

本题详细解读

1. 栈的基本概念

栈（Stack）是一种遵循**后进先出（LIFO）**原则的数据结构。栈的操作主要包括：

• push：将元素压入栈顶。
• pop：移除并返回栈顶元素。
• peek：返回栈顶元素但不移除。
• is_empty：判断栈是否为空。
• size：返回栈中元素的数量。

2. 使用数组实现栈

在Python中，数组可以通过列表（list）来实现。我们可以利用列表的append()和pop()方法来模拟栈的push和pop操作。

3. 代码解析

• __init__方法：初始化一个空列表self.stack作为栈的底层存储结构。
• push方法：使用append()方法将元素添加到列表的末尾，即栈顶。
• pop方法：使用pop()方法移除并返回列表的最后一个元素，即栈顶元素。如果栈为空，则抛出IndexError异常。
• peek方法：返回列表的最后一个元素，即栈顶元素。如果栈为空，则抛出IndexError异常。
• is_empty方法：检查列表的长度是否为0，判断栈是否为空。
• size方法：返回列表的长度，即栈中元素的数量。

4. 时间复杂度分析

• push操作：O(1)，因为append()操作在列表末尾添加元素的时间复杂度为O(1)。
• pop操作：O(1)，因为pop()操作在列表末尾移除元素的时间复杂度为O(1)。
• peek操作：O(1)，因为访问列表的最后一个元素的时间复杂度为O(1)。
• is_empty操作：O(1)，因为检查列表长度的时间复杂度为O(1)。
• size操作：O(1)，因为获取列表长度的时间复杂度为O(1)。

5. 使用示例

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 输出: 3
print(stack.peek())  # 输出: 2
print(stack.size())  # 输出: 2
print(stack.is_empty())  # 输出: False

通过上述代码，我们可以使用数组（列表）来实现一个栈，并且能够高效地执行栈的各种操作。