3.5. 用Python实现栈

3.5. Implementing a Stack in Python

原文: https://runestone.academy/ns/books/published/pythonds3/BasicDS/ImplementingaStackinPython.html?mode=browsing

中文英文

现在我们已经明确了栈作为抽象数据类型的定义，我们将关注使用 Python 实现栈。回顾一下，当我们给一个抽象数据类型一个物理实现时，我们称这种实现为数据结构。

正如我们在第一章所描述的，在 Python 中，与任何面向对象的编程语言一样，抽象数据类型如栈的实现选择是创建一个新的类。栈操作被实现为方法。此外，要实现栈（这是一个元素集合），利用 Python 提供的原始集合的力量和简单性是有意义的。我们将使用列表。

回顾一下，Python 的列表类提供了一个有序的集合机制和一组方法。例如，如果我们有一个列表 [2, 5, 3, 6, 7, 4]，我们只需决定哪个端被视为栈的顶部，哪个端是底部。一旦做出这个决定，可以使用列表方法如 append 和 pop 来实现操作。

以下栈实现（ActiveCode 1）假设列表的末端将保存栈的顶部元素。随着栈的增长（当 push 操作发生时），新项将被添加到列表的末端。 pop 操作将操作该末端。

class Stack:
    """使用列表实现栈"""

    def __init__(self):
        """创建新栈"""
        self._items = []

    def is_empty(self):
        """检查栈是否为空"""
        return not bool(self._items)

    def push(self, item):
        """将项添加到栈中"""
        self._items.append(item)

    def pop(self):
        """从栈中移除项"""
        return self._items.pop()

    def peek(self):
        """获取栈中顶部项的值"""
        return self._items[-1]

    def size(self):
        """获取栈中项的数量"""
        return len(self._items)

请记住，点击run按钮时不会发生任何事情，除了定义类。我们必须创建一个 Stack 对象，然后使用它。ActiveCode 2 显示了 Stack 类在我们执行 Table 1 中的操作序列时的实际情况。注意 Stack 类的定义从与本书材料一起提供的 pythonds3 模块中导入，或者可以从 Python Package Index 下载。

注意

pythonds3 模块包含本书中讨论的所有数据结构的实现。它根据以下部分进行结构化：基础、树和图。该模块可以从 GitHub 下载，或者通过命令行安装，如下所示：

python3 -m pip install -U pythonds3

from pythonds3.basic import Stack

s = Stack()

print(s.is_empty())
s.push(4)
s.push("dog")
print(s.peek())
s.push(True)
print(s.size())
print(s.is_empty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())

重要的是要注意，我们本可以选择使用列表实现栈，将顶部设置在开始处而不是末尾。在这种情况下，之前的 pop 和 append 方法将不再有效，我们将必须使用 pop 和 insert 明确索引位置 0（列表中的第一个项目）。该实现显示在 CodeLens 1 中。

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

    def is_empty(self):
        return self.items == []

    def push(self, item):
        self.items.insert(0, item)

    def pop(self):
        return self.items.pop(0)

    def peek(self):
        return self.items[0]

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

s = Stack()
s.push("hello")
s.push("true")
print(s.pop())

这种改变抽象数据类型的物理实现的能力，同时保持其逻辑特性，是抽象工作的一个例子。然而，即使栈可以以任意方式工作，如果考虑这两种实现的性能，确实存在差异。回顾一下，append() 和 pop() 操作都是 \(O(1)\) 的。这意味着第一种实现将以常数时间执行 push 和 pop 操作，无论栈中有多少项。第二种实现的性能较差，因为 insert(0) 和 pop(0) 操作都需要 \(O(n)\)，对于大小为 n 的栈来说。显然，即使实现逻辑上等效，它们在进行基准测试时的时间会有很大不同。

自我检查

Activity: 3.5.4 多项选择题Activity: 3.5.5 多项选择题

给定以下栈操作序列，当序列完成时，栈上的顶部项是什么？

:answer_a: "x" :answer_b: "y" :answer_c: "z" :answer_d: 栈为空

:correct: c

:feedback_a: 请记住，栈是从底部向上建立的。 :feedback_b: 请记住，栈是从底部向上建立的。 :feedback_c: 做得好。 :feedback_d: 请记住，栈是从底部向上建立的。

给定以下栈操作序列，当序列完成时，栈上的顶部项是什么？

m = Stack()
m.push("x")
m.push("y")
m.pop()
m.push("z")
m.peek()

• a: "x"
• b: 栈为空
• c: 将发生错误
• d: "z"

correct: c

• feedback a: 你可能需要查看一下 isEmpty 的文档
• feedback b: 栈中有奇数个项目，但每次循环中弹出两个项目。
• feedback c: 做得好。
• feedback d: 你可能需要查看一下 isEmpty 的文档

m = Stack()
m.push("x")
m.push("y")
m.push("z")
while not m.is_empty():
    m.pop()
    m.pop()

编写一个函数 rev_string(my_str)，该函数使用栈来反转字符串中的字符。

from test import testEqual
from pythonds3.basic import Stack

def rev_string(my_str):
    # 你的代码在这里

testEqual(rev_string("apple"), "elppa")
testEqual(rev_string("x"), "x")
testEqual(rev_string("1234567890"), "0987654321")

Now that we have clearly defined the stack as an abstract data type, we will turn our attention to using Python to implement the stack. Recall that when we give an abstract data type a physical implementation, we refer to the implementation as a data structure.

As we described in Chapter 1, in Python, as in any object-oriented programming language, the implementation of choice for an abstract data type such as a stack is the creation of a new class. The stack operations are implemented as methods. Further, to implement a stack, which is a collection of elements, it makes sense to utilize the power and simplicity of the primitive collections provided by Python. We will use a list.

Recall that the list class in Python provides an ordered collection mechanism and a set of methods. For example, if we have the list [2, 5, 3, 6, 7, 4], we need only to decide which end of the list will be considered the top of the stack and which will be the base. Once that decision is made, the operations can be implemented using the list methods such as append and pop.

The following stack implementation (ActiveCode 1) assumes that the end of the list will hold the top element of the stack. As the stack grows (as push operations occur), new items will be added on the end of the list. pop operations will manipulate that same end.

class Stack:
    """Stack implementation as a list"""

    def __init__(self):
        """Create new stack"""
        self._items = []

    def is_empty(self):
        """Check if the stack is empty"""
        return not bool(self._items)

    def push(self, item):
        """Add an item to the stack"""
        self._items.append(item)

    def pop(self):
        """Remove an item from the stack"""
        return self._items.pop()

    def peek(self):
        """Get the value of the top item in the stack"""
        return self._items[-1]

    def size(self):
        """Get the number of items in the stack"""
        return len(self._items)

Remember that nothing happens when we click the run button other than the definition of the class. We must create a Stack object and then use it. ActiveCode 2 shows the Stack class in action as we perform the sequence of operations from Table 1. Notice that the definition of the Stack class is imported from the pythonds3 module that is included with the materials for this book or can be downloaded from the Python Package Index.

Note

The pythonds3 module contains implementations of all data structures discussed in this book. It is structured according to the sections: basic, trees, and graphs. The module can be downloaded from GitHub or installed from the command line as follows:

python3 -m pip install -U pythonds3

from pythonds3.basic import Stack

s = Stack()

print(s.is_empty())
s.push(4)
s.push("dog")
print(s.peek())
s.push(True)
print(s.size())
print(s.is_empty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())

It is important to note that we could have chosen to implement the stack using a list where the top is at the beginning instead of at the end. In this case, the previous pop and append methods would no longer work and we would have to index position 0 (the first item in the list) explicitly using pop and insert. The implementation is shown in CodeLens 1.

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

    def is_empty(self):
        return self.items == []

    def push(self, item):
        self.items.insert(0, item)

    def pop(self):
        return self.items.pop(0)

    def peek(self):
        return self.items[0]

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

s = Stack()
s.push("hello")
s.push("true")
print(s.pop())

This ability to change the physical implementation of an abstract data type while maintaining the logical characteristics is an example of abstraction at work. However, even though the stack will work either way, if we consider the performance of the two implementations, there is definitely a difference. Recall that the append() and pop() operations were both \(O(1)\). This means that the first implementation will perform push and pop in constant time no matter how many items are on the stack. The performance of the second implementation suffers in that the insert(0) and pop(0) operations will both require \(O(n)\) for a stack of size n. Clearly, even though the implementations are logically equivalent, they would have very different timings when performing benchmark testing.

Self Check

Activity: 3.5.4 Multiple ChoiceActivity: 3.5.5 Multiple Choice

Given the following sequence of stack operations, what is the top item on the stack when the sequence is complete?

:answer_a: "x" :answer_b: "y" :answer_c: "z" :answer_d: The stack is empty

:correct: c

:feedback_a: Remember that a stack is built from the bottom up. :feedback_b: Remember that a stack is built from the bottom up. :feedback_c: Good job. :feedback_d: Remember that a stack is built from the bottom up.

Given the following sequence of stack operations, what is the top item on the stack when the sequence is complete?

m = Stack()
m.push("x")
m.push("y")
m.pop()
m.push("z")
m.peek()

• a: "x"
• b: the stack is empty
• c: an error will occur
• d: "z"

correct: c

• feedback a: You may want to check out the docs for isEmpty
• feedback b: There is an odd number of things on the stack but each time through the loop 2 things are popped.
• feedback c: Good Job.
• feedback d: You may want to check out the docs for isEmpty

m = Stack()
m.push("x")
m.push("y")
m.push("z")
while not m.is_empty():
    m.pop()
    m.pop()

Write a function rev_string(my_str) that uses a stack to reverse the characters in a string.

from test import testEqual
from pythonds3.basic import Stack

def rev_string(my_str):
    # your code here

testEqual(rev_string("apple"), "elppa")
testEqual(rev_string("x"), "x")
testEqual(rev_string("1234567890"), "0987654321")

---

最后更新: 2024年9月12日
创建日期: 2024年9月9日