栈

在本节课中，我们将学习栈数据结构及其在 Python 中的实现。

在后续课程中，我们会提供一些特定问题，这些问题特别适合使用栈来解决。我们将使用本节课所开发的实现来解决这些题目。

什么是栈？

首先，让我来描述一下什么是栈。从名字来看，这应该是一个相对熟悉的概念。

假设我们有四本书，书名分别是：

• A
• B
• C
• D

目前这些书散落在地板上，我们想把它们整齐地堆叠起来。

现在我们有了一个整齐的书堆！如果我们想从这个堆中取一本书，可以取最上面那本。从底部取书则比较危险，容易导致整个堆倒塌。因此，我们会取走栈顶的书，阅读或做任何想做的事情。

假设我们要取 书 A。目前它位于堆底，我们需要先取下 书 D，再取下 书 C 和 书 B，最后才能拿到 书 A。

这就是栈的核心思想。栈数据结构与我们日常生活中常见的物理堆非常相似。栈允许我们将任意编程元素、变量或对象放入其中，就像我们的书堆可以放书一样。

栈的操作

Push

向栈中插入元素的操作称为 push。当我们 push 一本书到栈上时，是将这本书放在原来栈顶的位置，使得新书成为新的栈顶元素。这就是 push 操作的含义：将元素压入栈中。我们向栈中添加元素，而最后一个被压入的元素就是新的栈顶。

Pop

栈还可以执行另一个操作，即弹出（pop）。弹出是指将栈顶的书取下来。这意味着当我们从栈中移除一个元素时，栈遵循“后进先出”（Last-In, First-Out）的原则。也就是说，最后插入的元素（即栈顶元素）在执行 pop 操作时会被移除。

Push 和 Pop 是这个数据结构所需的两个基本操作。

Peek

我们还可以查看栈顶元素，也就是可以向数据结构询问：“栈顶是什么？”然后通过 peek 操作获取该信息。注意，peek 操作不会移除栈顶元素，它只是返回该元素。

我们还可以检查栈是否为空，以及其他一些辅助功能，随着实现过程会逐步加入。

现在我将创建一个栈类，该类的构造函数将初始化一个 Python 列表。Python 列表具备我们所需的功能，这将使我们更容易调整其行为，使其符合我们对栈的预期——即支持 push 和 pop 操作。

1"""
2栈数据结构。
3"""
4class Stack():
5    def __init__(self):
6        self.items = []

我定义了一个名为 items 的类变量，并将其初始化为空列表。当创建栈对象时，self.items 就会被创建。接下来我们实现 push 方法：

1"""
2栈数据结构。
3"""
4class Stack():
5    def __init__(self):
6        self.items = []
7
8    def push(self, item):
9        self.items.append(item)

push 是该类的一个成员方法，接收一个 item 参数。在我们的例子中，这个 item 就是书名。我们将书名压入栈顶。

append 是 Python 列表的内置方法，用于将 item 添加到列表末尾。这正是我们在 push 方法中想要实现的行为。

1"""
2栈数据结构。
3"""
4class Stack():
5    def __init__(self):
6        self.items = []
7
8    def push(self, item):
9        self.items.append(item)
10
11    def pop(self):
12        return self.items.pop()

另一个需要实现的方法是 pop。由于我们基于列表实现，Python 提供了方便的 pop 方法，它会返回列表中最后一个插入的元素。

接下来，我们再添加几个额外的方法。但在那之前，先进行一次测试运行。

1"""
2栈数据结构。
3"""
4class Stack():
5    def __init__(self):
6        self.items = []
7
8    def push(self, item):
9        self.items.append(item)
10
11    def pop(self):
12        return self.items.pop()
13
14    def get_stack(self):
15        return self.items
16
17myStack = Stack()
18myStack.push("A")
19myStack.push("B")
20print(myStack.get_stack())
21myStack.push("C")
22print(myStack.get_stack())
23myStack.pop()
24print(myStack.get_stack())

我们定义了一个名为 get_stack() 的方法，用于返回构成栈核心的 items 列表。
然后在第 17 行创建了一个栈对象 myStack，并依次压入 "A" 和 "B"（第 18-19 行）。此时打印 myStack，输出为 ['A', 'B']。其中 "A" 在栈底，"B" 在栈顶。接着在第 21 行压入 "C"，输出变为 ['A', 'B', 'C']，说明 "C" 成为了栈顶。

至此，我们已经掌握了栈的核心原理。此外，我们还可以添加一些有用的辅助方法，比如 is_empty，用于判断栈是否为空。

1"""
2栈数据结构。
3"""
4class Stack():
5    def __init__(self):
6        self.items = []
7
8    def push(self, item):
9        self.items.append(item)
10
11    def pop(self):
12        return self.items.pop()
13
14    def is_empty(self):
15        return self.items == []
16
17    def get_stack(self):
18        return self.items
19
20myStack = Stack()
21print(myStack.is_empty())

此时输出为 True，因为栈中还没有任何元素。如果我们先压入一个元素再调用 is_empty()，结果应为 False。你可以自己尝试验证。

1"""
2栈数据结构。
3"""
4class Stack():
5    def __init__(self):
6        self.items = []
7
8    def push(self, item):
9        self.items.append(item)
10
11    def pop(self):
12        return self.items.pop()
13
14    def is_empty(self):
15        return self.items == []
16
17    def peek(self):
18        if not self.is_empty():
19            return self.items[-1]
20
21    def get_stack(self):
22        return self.items
23
24myStack = Stack()
25myStack.push("A")
26myStack.push("B")
27myStack.push("C")
28myStack.push("D")
29print(myStack.peek())

现在我们在第 17 行添加了 peek 操作，用于查看栈顶元素。

在上述代码中，如果调用 peek，应该返回 D。peek 方法首先检查栈是否为空（第 18 行），如果不为空，则返回列表的最后一个元素，也就是栈顶元素。我们通过 self.items[-1]（Python 中表示列表最后一个元素）来获取该值。因此，最初返回的是 D，即 Python 认为栈顶的元素。

注意：你也可以在之前实现的方法中检查栈是否为空。但为了简化逻辑，这里省略了这部分检查。

现在你可以动手创建一个栈对象。不必局限于字母或字符串，也可以压入数字。多尝试不同的操作，感受一下这个数据结构的工作方式。下一节课见。