栈

6.1 栈的定义及其特性

栈 是一种抽象的数据结构，表示一个按 "后进先出" 原则组织的元素集合 (Last In, First Out, LIFO)。可以将栈想象成一堆书：最后添加的书在顶部，将会首先移除/取走。

栈的特性：

• LIFO (Last In, First Out): 最后添加的元素最先提取。
• 受限操作: 栈只支持添加 (push), 删除 (pop) 和查看 (peek) 顶部元素。
• 单向访问: 只能从栈顶访问元素。
• 简单实现: 栈可以通过数组或链表轻松实现。
• 内存管理: 临时数据或状态可以按相反顺序存储和提取。

LIFO 工作原理：

• 添加元素 (push): 新元素被添加到栈顶。
• 删除元素 (pop): 最后添加的元素从栈顶移除。
• 查看栈顶 (peek): 查看栈顶元素而不移除它。

栈的元素从一侧添加和移除，称为顶部（top）。因此，最后添加的元素总是在顶部，将会最先被移除。

6.2 主要操作

主要操作: push, pop, peek

操作 push: 添加新元素至栈顶。

时间复杂度: O(1).

使用 Python 中的 list 类模拟栈的示例：

stack = []
stack.append(10)  # push 10
stack.append(20)  # push 20
print(stack)  # 输出: [10, 20]

操作 pop: 删除并返回栈顶的元素。

时间复杂度: O(1).

使用 Python 中的 list 类模拟栈的示例：

stack = []
stack.append(10)  # push 10
stack.append(20)  # push 20

top_element = stack.pop()  # pop
print(top_element)  # 输出: 20
print(stack)  # 输出: [10]

操作 peek: 返回栈顶的元素而不删除。

时间复杂度: O(1).

实现示例：

stack = []
stack.append(10)  # push 10

top_element = stack[-1]  # peek
print(top_element)  # 输出: 10

6.3 栈的使用示例

让我们来看几个栈的使用示例：

函数调用管理

在 Python 中，栈用于在程序执行时跟踪函数。每次调用函数时，返回地址和局部变量都会被放入栈中。当函数完成执行时，控制权返回到调用它的函数，数据从栈中提取。

调用栈使用示例：

在这个示例中，factorial 函数的递归调用使用调用栈来存储每次调用的状态，直到达到基准条件 (n == 1)。

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # 输出: 120

撤销操作 (Undo)

栈用于在文本编辑器和其他应用中实现撤销操作的功能。当用户执行操作时，它会被保存到栈中。当执行 Undo 操作时，最后一个操作从栈中提取并撤销。

使用栈进行撤销操作的示例：

class TextEditor:
    def __init__(self):
        self.text = ""
        self.history = []

    def type(self, text):
        self.history.append(self.text)
        self.text += text

    def undo(self):
        if self.history:
            self.text = self.history.pop()

# 使用示例:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text)  # 输出: "Hello World"
editor.undo()
print(editor.text)  # 输出: "Hello"
editor.undo()
print(editor.text)  # 输出: ""

1

Опрос

算法入门,  51 уровень,  5 лекция

недоступен

算法入门

算法入门

Открыть