Problem Solving with Algorithms and Data Structures using Python.使用Python解决算法和数据结构的问题。
By Brad Miller and David Ranum, Luther College
目录：
4.1. Objectives
4.1. 目的
To understand the abstract data types stack, queue, deque, and list.
理解抽象数据类型stack、queue、deque和list。
To be able to implement the ADTs stack, queue, and deque using Python lists.
能够使用Python列表实现ADTs堆栈、队列和deque。
To understand the performance of the implementations of basic linear data structures.
了解基本线性数据结构实现的性能。
To understand prefix, infix, and postfix expression formats.
理解前缀、中缀和后缀表达式格式。
To use stacks to evaluate postfix expressions.
使用栈来计算后缀表达式。
To use stacks to convert expressions from infix to postfix.
使用堆栈将表达式从中缀转换为后缀。
To use queues for basic timing simulations.
使用队列进行基本定时模拟。
To be able to recognize problem properties where stacks, queues, and deques are appropriate data structures.
能够识别栈、队列和队列是合适的数据结构的问题属性。
To be able to implement the abstract data type list as a linked list using the node and reference pattern.
能够使用node和reference模式将抽象数据类型列表实现为一个链表。
To be able to compare the performance of our linked list implementation with Python’s list implementation.
为了能够比较我们的链表实现与Python的链表实现的性能。
4.2. What Are Linear Structures?
4.2. 什么是线性数据结构？
We will begin our study of data structures by considering four simple but very powerful concepts.
我们将从四个简单但非常强大的概念开始研究数据结构。
Stacks, queues, deques, and lists are examples of data collections whose items are ordered depending on how they are added or removed.
堆栈、队列、deque和列表都是数据集合的例子，它们的项根据如何添加或删除而排序。
Once an item is added, it stays in that position relative to the other elements that came before and came after it.
一旦添加了一个项，它就会保持相对于它之前和之后的其他元素的位置。
Collections such as these are often referred to as linear data structures.
像这样的集合通常被称为线性数据结构。
Linear structures can be thought of as having two ends.
线性结构可以被认为有两个端点。
Sometimes these ends are referred to as the “left” and the “right” or in some cases the “front” and the “rear.”
有时这些末端被称为“左”和“右”，或者在某些情况下是“前”和“后”。
You could also call them the “top” and the “bottom.”
你也可以称它们为“顶部”和“底部”。
The names given to the ends are not significant.
给末尾的名称没有意义。
What distinguishes one linear structure from another is the way in which items are added and removed, in particular the location where these additions and removals occur.
一个线性结构与另一个线性结构的区别在于添加和删除物品的方式，特别是添加和删除物品的地点。
For example, a structure might allow new items to be added at only one end.
例如，一个结构可能只允许在一端添加新项。
Some structures might allow items to be removed from either end.
有些结构可能允许从两端移除物品。
These variations give rise to some of the most useful data structures in computer science.
这些变化产生了计算机科学中一些最有用的数据结构。
They appear in many algorithms and can be used to solve a variety of important problems.
它们出现在许多算法中，可以用来解决各种重要的问题。
4.3. What is a Stack?
4.3. 什么是堆栈?
A stack (sometimes called a “push-down stack”) is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end.
堆栈(有时称为“下推堆栈”)是项目的有序集合，其中添加新项目和删除现有项目总是在同一端进行。
This end is commonly referred to as the “top.”
这一端通常被称为“顶部”。
The end opposite the top is known as the “base.”
与顶部相对的末端被称为“底部”。
The base of the stack is significant since items stored in the stack that are closer to the base represent those that have been in the stack the longest.
堆栈的基部是重要的，因为存储在堆栈中离基部较近的项表示在堆栈中待的时间最长的项。
The most recently added item is the one that is in position to be removed first.
最近添加的项目是首先要删除的项目。
This ordering principle is sometimes called LIFO, last-in first-out.
这种排序原则有时被称为后进先出(LIFO)。
It provides an ordering based on length of time in the collection.
它提供基于集合中时间长度的排序。
Newer items are near the top, while older items are near the base.
更新的项目在顶部，而旧的项目在底部。
Many examples of stacks occur in everyday situations.
许多堆栈的例子出现在日常生活中。
Almost any cafeteria has a stack of trays or plates where you take the one at the top, uncovering a new tray or plate for the next customer in line.
几乎所有的自助餐厅都有一堆托盘或盘子，你拿上最上面的一个，为下一个顾客打开一个新的托盘或盘子。
Imagine a stack of books on a desk (Figure 1).
想象一下桌子上有一堆书(图1)。
The only book whose cover is visible is the one on top.
唯一能看到封面的书是最上面的那本书。
To access others in the stack, we need to remove the ones that are sitting on top of them.
要访问堆栈中的其他元素，我们需要删除位于它们之上的元素。
Figure 2 shows another stack.
图2显示了另一个堆栈。
This one contains a number of primitive Python data objects.
它包含了许多基本的Python数据对象。
Figure 1: A Stack of Books
图1:一堆书
Figure 2: A Stack of Primitive Python Objects
图2:原始Python对象的堆栈
One of the most useful ideas related to stacks comes from the simple observation of items as they are added and then removed.
关于栈最有用的一个想法来自于对添加和删除项的简单观察。
Assume you start out with a clean desktop.
假设您从一个干净的桌面开始。
Now place books one at a time on top of each other.
现在把书一个一个地放在另一个上面。
You are constructing a stack.
您正在构建一个堆栈。
Consider what happens when you begin removing books.
考虑一下当你开始删除书籍时会发生什么。
The order that they are removed is exactly the reverse of the order that they were placed.
它们被删除的顺序与它们被放置的顺序正好相反。
Stacks are fundamentally important, as they can be used to reverse the order of items.
栈是非常重要的，因为它们可以用来颠倒项目的顺序。
The order of insertion is the reverse of the order of removal.
插入的顺序与删除的顺序相反。
Figure 3 shows the Python data object stack as it was created and then again as items are removed.
图3显示了Python数据对象堆栈创建时和删除项时的情况。
Note the order of the objects.
注意对象的顺序。
Figure 3: The Reversal Property of Stacks
图3:栈的反转属性
Considering this reversal property, you can perhaps think of examples of stacks that occur as you use your computer.
考虑到这个反转属性，您可以考虑使用计算机时出现的堆栈示例。
For example, every web browser has a Back button.
例如，每个web浏览器都有一个后退按钮。
As you navigate from web page to web page, those pages are placed on a stack (actually it is the URLs that are going on the stack).
当您从一个web页面导航到另一个web页面时，这些页面被放置在一个堆栈上(实际上它是在堆栈上的url)。
The current page that you are viewing is on the top and the first page you looked at is at the base.
您正在查看的当前页面位于顶部，而您查看的第一页位于底部。
If you click on the Back button, you begin to move in reverse order through the pages.
如果你点击后退按钮，你就会开始以相反的顺序在页面中移动。
4.4. The Stack Abstract Data Type
4.4. 堆栈抽象数据类型
The stack abstract data type is defined by the following structure and operations.
栈抽象数据类型由以下结构和操作定义。
A stack is structured, as described above, as an ordered collection of items where items are added to and removed from the end called the “top.”
如上面所述，堆栈的结构是一个有序的项集合，其中的项被添加到称为“top”的末端，并从末端移除。
Stacks are ordered LIFO.
堆栈是后进先出排序的。
The stack operations are given below.
堆栈操作如下所示。
-
Stack()creates a new stack that is empty. It needs no parameters and returns an empty stack.
Stack()创建一个空的新堆栈。它不需要参数，并返回一个空堆栈。 -
push(item)adds a new item to the top of the stack. It needs the item and returns nothing.
push(item)将一个新项目添加到堆栈的顶部。它需要该项目，但不返回任何内容。 -
pop()removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
pop()从堆栈中移除顶部的项。它不需要参数并返回该项。栈被修改。 -
peek()returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
peek()返回栈顶项，但不移除它。它不需要参数。堆栈没有被修改。 -
isEmpty()tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
isEmpty()测试堆栈是否为空。它不需要参数并返回一个布尔值。 -
size()returns the number of items on the stack. It needs no parameters and returns an integer.
size()返回栈上的项数。它不需要参数并返回一个整数。
For example, if s is a stack that has been created and starts out empty, then Table 1 shows the results of a sequence of stack operations.
例如，如果’ s '是一个已经创建的堆栈，并且一开始是空的，那么表1显示了一系列堆栈操作的结果。
Under stack contents, the top item is listed at the far right.
在堆栈内容下面，最顶端的项目列在最右边。
Table 1: Sample Stack Operations
表1:堆栈操作示例
| Stack Operation 堆栈操作 | Stack Contents 栈内容 | Return Value 返回值 |
|---|---|---|
| s.isEmpty() | [] | True |
| s.push(4) | [4] | |
| s.push(‘dog’) | [4,‘dog’] | |
| s.peek() | [4,‘dog’] | ‘dog’ |
| s.push(True) | [4,‘dog’,True] | |
| s.size() | [4,‘dog’,True] | 3 |
| s.isEmpty() | [4,‘dog’,True] | False |
| s.push(8.4) | [4,‘dog’,True,8.4] | |
| s.pop() | [4,‘dog’,True] | 8.4 |
| s.pop() | [4,‘dog’] | True |
| s.size() | [4,‘dog’] | 2 |