Python 数据结构和算法实用指南（二）（1）https://developer.aliyun.com/article/1507549
追加元素
要在单链表循环列表中追加一个元素，我们只需包含一个新功能，使新添加或追加的节点指向tail节点。这在以下代码中得到了演示。与单链表实现相比，多了一行额外的代码，如粗体所示：
def append(self, data): node = Node(data) if self.head: self.head.next = node self.head = node else: self.head = node self.tail = node self.head.next = self.tail self.size += 1
在循环列表中删除元素
要删除循环列表中的一个节点，看起来我们可以类似于在追加操作中所做的方式来做。只需确保head指向tail。在删除操作中只有一行需要更改。只有当我们删除tail节点时，我们需要确保head节点被更新为指向新的尾节点。这将给我们以下实现（粗体字代码行是单链表中删除操作实现的一个补充）：
def delete(self, data): current = self.tail prev = self.tail while current: if current.data == data: if current == self.tail: self.tail = current.next self.head.next = self.tail else: prev.next = current.next self.size -= 1 return prev = current current = current.next
然而，这段代码存在一个严重的问题。在循环列表的情况下，我们不能循环直到current变成None，因为在循环链表的情况下，当前节点永远不会指向None。如果删除一个现有节点，你不会看到这一点，但是尝试删除一个不存在的节点，你将陷入无限循环。
因此，我们需要找到一种不同的方法来控制while循环。我们不能检查current是否已经到达head，因为那样它永远不会检查最后一个节点。但我们可以使用prev，因为它比current落后一个节点。然而，有一个特殊情况。在第一个循环迭代中，current和prev将指向相同的节点，即尾节点。我们希望确保循环在这里运行，因为我们需要考虑单节点列表。更新后的删除方法现在如下所示：
def delete(self, data): current = self.tail prev = self.tail while prev == current or prev != self.head: if current.data == data: if current == self.tail: self.tail = current.next self.head.next = self.tail else: prev.next = current.next self.size -= 1 return prev = current current = current.next
遍历循环列表
遍历循环链表非常方便，因为我们不需要寻找起始点。我们可以从任何地方开始，只需要在再次到达相同节点时小心停止遍历。我们可以使用我们在本章开头讨论过的iter()方法。它应该适用于我们的循环列表；唯一的区别是在遍历循环列表时，我们必须提及一个退出条件，否则程序将陷入循环并无限运行。我们可以通过使用一个计数变量来创建一个退出条件。考虑以下示例代码：
words = CircularList() words.append('eggs') words.append('ham') words.append('spam') counter = 0 for word in words.iter(): print(word) counter += 1 if counter > 1000: break
一旦我们打印出 1,000 个元素，我们就会跳出循环。
总结
在本章中，我们研究了链表。我们学习了列表的基本概念，如节点和指向其他节点的指针。我们实现了这些类型列表中发生的主要操作，并看到了最坏情况的运行时间是如何比较的。
在下一章中，我们将看两种通常使用列表实现的其他数据结构——栈和队列。
第五章：栈和队列
在本章中，我们将在上一章学到的技能基础上创建特殊的列表实现。我们仍然坚持使用线性结构。在接下来的章节中，我们将深入了解更复杂的数据结构的细节。
在本章中，我们将了解栈和队列的概念。我们还将使用各种方法在 Python 中实现这些数据结构，如lists和node。
在本章中，我们将涵盖以下内容：
- 使用各种方法实现栈和队列
- 栈和队列的一些真实应用示例
技术要求
你应该有一台安装了 Python 的计算机系统。本章讨论的概念的所有程序都在书中提供，也可以在以下链接的 GitHub 存储库中找到：github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter05。
栈
栈是一种存储数据的数据结构，类似于厨房里的一堆盘子。你可以把一个盘子放在栈的顶部，当你需要一个盘子时，你从栈的顶部拿走它。最后添加到栈上的盘子将首先从栈中取出。同样，栈数据结构允许我们从一端存储和读取数据，最后添加的元素首先被取出。因此，栈是一种后进先出（LIFO）结构：
前面的图表描述了一堆盘子。只有将一个盘子放在堆的顶部才有可能添加一个盘子。从盘子堆中移除一个盘子意味着移除堆顶上的盘子。
栈上执行的两个主要操作是push和pop。当元素被添加到栈顶时，它被推送到栈上。当要从栈顶取出元素时，它被弹出栈。有时使用的另一个操作是peek，它可以查看栈顶的元素而不将其弹出。
栈用于许多事情。栈的一个非常常见的用途是在函数调用期间跟踪返回地址。假设我们有以下程序：
def b(): print('b') def a(): b() a() print("done")
当程序执行到a()的调用时，发生以下情况：
- 首先将当前指令的地址推送到栈上，然后跳转到
a的定义 - 在函数
a()内部，调用函数b() - 函数
b()的返回地址被推送到栈上 - 一旦
b()函数和函数执行完毕，返回地址将从栈中弹出，这将带我们回到函数a()。 - 当函数
a中的所有指令完成时，返回地址再次从栈中弹出，这将带我们回到main函数和print语句
栈也用于在函数之间传递数据。考虑以下示例。假设你的代码中有以下函数调用：
somefunc(14, 'eggs', 'ham', 'spam')
内部发生的是，函数传递的值14, 'eggs', 'ham'和'spam'将依次被推送到栈上，如下图所示：
当代码调用jump到函数定义时，a, b, c, d的值将从栈中弹出。首先弹出spam元素并赋值给d，然后将ham赋值给c，依此类推：
def somefunc(a, b, c, d): print("function executed")
栈实现
栈可以使用节点在 Python 中实现。我们首先创建一个node类，就像在上一章中使用列表一样：
class Node: def __init__(self, data=None): self.data = data self.next = None
正如我们讨论的，一个节点包含数据和列表中下一个项目的引用。在这里，我们将实现一个栈而不是列表；然而，节点的相同原则在这里也适用——节点通过引用链接在一起。
现在让我们来看一下stack类。它的开始方式与单链表类似。我们需要两样东西来实现使用节点的栈：
- 首先，我们需要知道位于栈顶的节点，以便我们能够通过这个节点应用
push和pop操作。 - 我们还希望跟踪栈中节点的数量，因此我们向栈类添加一个
size变量。考虑以下代码片段用于栈类：
class Stack: def __init__(self): self.top = None self.size = 0
推送操作
push操作是栈上的一个重要操作；它用于在栈顶添加一个元素。我们在 Python 中实现推送功能以了解它是如何工作的。首先，我们检查栈是否已经有一些项目或者它是空的，当我们希望在栈中添加一个新节点时。
如果栈已经有一些元素，那么我们需要做两件事：
- 新节点必须使其下一个指针指向先前位于顶部的节点。
- 我们通过将
self.top指向新添加的节点，将这个新节点放在栈的顶部。请参阅以下图表中的两条指令：
如果现有栈为空，并且要添加的新节点是第一个元素，我们需要将此节点作为元素的顶部节点。因此，self.top将指向这个新节点。请参阅以下图表：
以下是stack中push操作的完整实现：
def push(self, data): node = Node(data) if self.top: node.next = self.top self.top = node else: self.top = node self.size += 1
弹出操作
现在，我们需要栈的另一个重要功能，那就是pop操作。它读取栈的顶部元素并将其从栈中移除。pop操作返回栈的顶部元素，并且如果栈为空则返回None。
要在栈上实现pop操作：
- 首先，检查栈是否为空。在空栈上不允许
pop操作。 - 如果栈不为空，可以检查顶部节点是否具有其
next属性指向其他节点。这意味着栈中有元素，并且顶部节点指向栈中的下一个节点。要应用pop操作，我们必须更改顶部指针。下一个节点应该在顶部。我们通过将self.top指向self.top.next来实现这一点。请参阅以下图表以了解这一点：
- 当栈中只有一个节点时，在弹出操作后栈将为空。我们必须将顶部指针更改为
None。见下图：
- 移除这样一个节点会导致
self.top指向None：
- 如果栈不为空，如果栈的顶部节点具有其
next属性指向其他节点，则可以将栈的大小减少1。以下是 Python 中stack的pop操作的完整代码：
def pop(self): if self.top: data = self.top.data self.size -= 1 if self.top.next: self.top = self.top.next else: self.top = None return data else: return None
查看操作
还有另一个可以应用在栈上的重要操作——peek方法。这个方法返回栈顶的元素，而不从栈中删除它。peek和pop之间唯一的区别是，peek方法只返回顶部元素；然而，在pop方法的情况下，顶部元素被返回并且也从栈中删除。
弹出操作允许我们查看顶部元素而不改变栈。这个操作非常简单。如果有顶部元素，则返回其数据；否则，返回None（因此，peek的行为与pop相匹配）：
def peek(self): if self.top return self.top.data else: return None
括号匹配应用
现在让我们看一个示例应用程序，展示我们如何使用我们的堆栈实现。我们将编写一个小函数，用于验证包含括号（(，[或{）的语句是否平衡，即关闭括号的数量是否与开放括号的数量匹配。它还将确保一个括号对确实包含在另一个括号中：
def check_brackets(statement): stack = Stack() for ch in statement: if ch in ('{', '[', '('): stack.push(ch) if ch in ('}', ']', ')'): last = stack.pop() if last is '{' and ch is '}': continue elif last is '[' and ch is ']': continue elif last is '(' and ch is ')': continue else: return False if stack.size > 0: return False else: return True
我们的函数解析传递给它的语句中的每个字符。如果它得到一个开放括号，它将其推送到堆栈上。如果它得到一个关闭括号，它将堆栈的顶部元素弹出并比较两个括号，以确保它们的类型匹配，(应该匹配)，[应该匹配]，{应该匹配}。如果它们不匹配，我们返回False；否则，我们继续解析。
一旦我们到达语句的末尾，我们需要进行最后一次检查。如果堆栈为空，那么很好，我们可以返回True。但是如果堆栈不为空，那么我们有一个没有匹配的关闭括号，我们将返回False。我们可以使用以下代码测试括号匹配器：
sl = ( "{(foo)(bar)}hellois)a)test", "{(foo)(bar)}hellois)atest", "{(foo)(bar)}hellois)a)test))" ) for s in sl: m = check_brackets(s) print("{}: {}".format(s, m))
只有三个语句中的第一个应该匹配。当我们运行代码时，我们得到以下输出：
上述代码的输出是True，False和False。
总之，堆栈数据结构的push和pop操作吸引了*O(1)*的复杂性。堆栈数据结构很简单；然而，它被用于实现许多真实世界应用中的功能。浏览器中的后退和前进按钮是使用堆栈实现的。堆栈也用于实现文字处理器中的撤销和重做功能。
队列
另一种特殊的列表类型是队列数据结构。队列数据结构非常类似于你在现实生活中习惯的常规队列。如果你曾经在机场排队或在邻里商店排队等待你最喜欢的汉堡，那么你应该知道队列是如何工作的。
队列是非常基础和重要的概念，因为许多其他数据结构都是建立在它们之上的。
队列的工作方式如下。通常，第一个加入队列的人会首先被服务，每个人都将按照加入队列的顺序被服务。首先进入，先出的首字母缩写 FIFO 最好地解释了队列的概念。FIFO代表先进先出。当人们站在队列中等待轮到他们被服务时，服务只在队列的前端提供。人们只有在被服务时才会离开队列，这只会发生在队列的最前面。请参见以下图表，其中人们站在队列中，最前面的人将首先被服务：
要加入队列，参与者必须站在队列中的最后一个人后面。这是队列接受新成员的唯一合法方式。队列的长度并不重要。
我们将提供各种队列的实现，但这将围绕 FIFO 的相同概念。首先添加的项目将首先被读取。我们将称添加元素到队列的操作为enqueue。当我们从队列中删除一个元素时，我们将称之为dequeue操作。每当一个元素被入队时，队列的长度或大小增加 1。相反，出队的项目会减少队列中的元素数量 1。
为了演示这两个操作，以下表格显示了从队列中添加和删除元素的效果：
| 队列操作 | 大小 | 内容 | 操作结果 |
Queue() |
0 | [] |
创建了一个空的队列对象。 |
Enqueue Packt |
1 | ['Packt'] |
队列中添加了一个 Packt 项目。 |
Enqueue 发布 |
2 | ['发布', 'Packt'] |
队列中添加了一个 发布 项目。 |
Size() |
2 | ['Publishing', 'Packt'] |
返回队列中的项目数，在此示例中为 2。 |
Dequeue() |
1 | ['Publishing'] |
Packt项目被出队并返回。（这个项目是第一个添加的，所以它被第一个移除。） |
Dequeue() |
0 | [] |
Publishing项目被出队并返回。（这是最后添加的项目，所以最后返回。） |
基于列表的队列
队列可以使用各种方法实现，例如list、stack和node。我们将逐一讨论使用所有这些方法实现队列的方法。让我们从使用 Python 的list类实现队列开始。这有助于我们快速了解队列。必须在队列上执行的操作封装在ListQueue类中：
class ListQueue: def __init__(self): self.items = [] self.size = 0
在初始化方法__init__中，items实例变量设置为[]，这意味着创建时队列为空。队列的大小也设置为零。enqueue和dequeue是队列中重要的方法，我们将在下一小节中讨论它们。
入队操作
enqueue操作将项目添加到队列中。它使用list类的insert方法在列表的前面插入项目（或数据）。请参阅以下代码以实现enqueue方法：
def enqueue(self, data): self.items.insert(0, data) # Always insert items at index 0 self.size += 1 # increment the size of the queue by 1
重要的是要注意我们如何使用列表实现队列中的插入。概念是我们在列表的索引0处添加项目；这是数组或列表中的第一个位置。要理解在列表的索引0处添加项目时队列的工作原理的概念，请考虑以下图表。我们从一个空列表开始。最初，我们在索引0处添加一个项目1。接下来，我们在索引0处添加一个项目2；它将先前添加的项目移动到下一个索引。
接下来，当我们再次在索引0处向列表中添加一个新项目3时，已添加到列表中的所有项目都会被移动，如下图所示。同样，当我们在索引0处添加项目4时，列表中的所有项目都会被移动：
因此，在我们使用 Python 列表实现队列时，数组索引0是唯一可以向队列中插入新数据元素的位置。insert操作将列表中现有的数据元素向上移动一个位置，然后将新数据插入到索引0处创建的空间中。
为了使我们的队列反映新元素的添加，大小增加了1：
self.size += 1
我们可以使用 Python 列表的shift方法作为在0处实现插入的另一种方法。
出队操作
dequeue操作用于从队列中删除项目。该方法返回队列中的顶部项目并将其从队列中删除。以下是dequeue方法的实现：
def dequeue(self): data = self.items.pop() # delete the topmost item from the queue self.size -= 1 # decrement the size of the queue by 1 return data
Python 的list类有一个名为pop()的方法。pop方法执行以下操作：
- 从列表中删除最后一个项目
- 将从列表中删除的项目返回给用户或调用它的代码
列表中的最后一个项目被弹出并保存在data变量中。在方法的最后一行，返回数据。
考虑以下图表作为我们的队列实现，其中添加了三个元素—1、2和3。执行dequeue操作时，数据为1的节点从队列的前面移除，因为它是最先添加的：
队列中的结果元素如下所示：
由于一个原因，enqueue操作非常低效。该方法必须首先将所有元素向前移动一个空间。想象一下，列表中有 100 万个元素需要在每次向队列添加新元素时进行移动。这将使大型列表的入队过程非常缓慢。
基于堆栈的队列
队列也可以使用两个栈来实现。我们最初设置了两个实例变量来在初始化时创建一个空队列。这些是帮助我们实现队列的栈。在这种情况下，栈只是允许我们在其上调用push和pop方法的 Python 列表，最终允许我们获得enqueue和dequeue操作的功能。以下是Queue类：
class Queue: def __init__(self): self.inbound_stack = [] self.outbound_stack = []
inbound_stack只用于存储添加到队列中的元素。不能对此堆栈执行其他操作。
入队操作
enqueue方法用于向队列中添加项目。这个方法非常简单，只接收要附加到队列的data。然后将此数据传递给queue类中inbound_stack的append方法。此外，append方法用于模拟push操作，将元素推送到栈的顶部。以下代码是使用 Python 中的栈实现enqueue的方法：
def enqueue(self, data): self.inbound_stack.append(data)
要将数据enqueue到inbound_stack，以下代码可以完成任务：
queue = Queue() queue.enqueue(5) queue.enqueue(6) queue.enqueue(7) print(queue.inbound_stack)
队列中inbound_stack的命令行输出如下：
[5, 6, 7]
出队操作
dequeue操作用于按添加的项目顺序从队列中删除元素。添加到我们的队列中的新元素最终会出现在inbound_stack中。我们不是从inbound_stack中删除元素，而是将注意力转移到另一个栈，即outbound_stack。我们只能通过outbound_stack删除队列中的元素。
为了理解outbound_stack如何用于从队列中删除项目，让我们考虑以下示例。
最初，我们的inbound_stack填充了元素5、6和7，如下图所示：
我们首先检查outbound_stack是否为空。由于开始时它是空的，我们使用pop操作将inbound_stack的所有元素移动到outbound_stack。现在inbound_stack变为空，而outbound_stack保留元素。我们在下图中展示了这一点，以便更清楚地理解：
现在，如果outbound_stack不为空，我们继续使用pop操作从队列中删除项目。在前面的图中，当我们对outbound_stack应用pop操作时，我们得到了元素5，这是正确的，因为它是第一个添加的元素，应该是从队列中弹出的第一个元素。这样outbound_stack就只剩下两个元素了：
以下是队列的dequeue方法的实现：
def dequeue(self): if not self.outbound_stack: while self.inbound_stack: self.outbound_stack.append(self.inbound_stack.pop()) return self.outbound_stack.pop()
if语句首先检查outbound_stack是否为空。如果不为空，我们继续使用pop方法删除队列前端的元素，如下所示：
return self.outbound_stack.pop()
如果outbound_stack为空，那么在弹出队列的前端元素之前，inbound_stack中的所有元素都将移动到outbound_stack中：
while self.inbound_stack: self.outbound_stack.append(self.inbound_stack.pop())
while循环将在inbound_stack中有元素的情况下继续执行。
self.inbound_stack.pop()语句将删除添加到inbound_stack的最新元素，并立即将弹出的数据传递给self.outbound_stack.append()方法调用。
让我们考虑一个示例代码，以理解队列上的操作。我们首先使用队列实现向队列中添加三个项目，即5、6和7。接下来，我们应用dequeue操作从队列中删除项目。以下是代码：
queue = Queue() queue.enqueue(5) queue.enqueue(6) queue.enqueue(7) print(queue.inbound_stack) queue.dequeue() print(queue.inbound_stack) print(queue.outbound_stack) queue.dequeue() print(queue.outbound_stack)
上述代码的输出如下：
[5, 6, 7] [] [7, 6] [7]
前面的代码片段首先向队列添加元素，并打印出队列中的元素。接下来调用dequeue方法，然后再次打印队列时观察到元素数量的变化。
使用两个栈实现队列非常重要，关于这个问题在面试中经常被提出。
Python 数据结构和算法实用指南（二）（3）https://developer.aliyun.com/article/1507562
