在本章中，我们将在上一章中学习的技能的基础上，创建特殊列表实现。我们仍然坚持线性结构。在接下来的章节中，我们将讨论更复杂的数据结构。
在本章中，我们将了解以下内容：
- 实现栈和队列
- 栈和队列的一些应用
栈是一种数据结构，通常被比作一堆板。如果你刚洗过一个盘子，你就把它放在盘子的上面。当你需要一个盘子时，你可以把它从盘子的顶部取下来。因此，要添加到栈中的最后一块板将是第一块从栈中移除的板。因此，栈是一种后进先出（后进先出结构：
上图描绘了一堆板。只有将板留在桩的顶部，才能将板添加到桩中。从板材堆中移除板材意味着移除位于板材堆顶部的板材。
在栈上有两个主要操作：push和pop。将元素添加到栈顶部时，它将被推送到栈上。当元素从栈顶部取出时，它将从栈中弹出。有时使用的另一个操作是peek，它可以在不弹出的情况下看到栈上的元素。
栈用于许多事情。栈的一个常见用法是在函数调用期间跟踪返回地址。让我们想象一下，我们有以下小程序：
def b():
print('b')
def a():
b()
a()
print("done") 当程序执行到达对a()的调用时，它首先将以下指令的地址推送到栈上，然后跳到a。在a内部调用b()，但在此之前，返回地址被推送到栈上。一旦进入b()并完成该功能，返回地址就会从栈中弹出，这会将我们带回a()。当a完成时，返回地址从栈中弹出，这使我们回到print语句。
栈实际上也用于在函数之间传递数据。假设您的代码中有以下函数调用：
somefunc(14, 'eggs', 'ham', 'spam') 将要发生的是14, 'eggs', 'ham'和'spam'将被推到栈上，一次推一个：
当代码跳入函数时，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课程。它的开头类似于一个单链表。我们需要知道栈顶部的节点。我们还希望跟踪栈中的节点数。因此，我们将向类中添加以下字段：
class Stack:
def __init__(self):
self.top = None
self.size = 0 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 在下图中，创建新节点后没有现有节点。因此self.top将指向这个新节点。if语句的 else 部分保证发生以下情况：
在一个已有栈的场景中，我们移动self.top，使其指向新创建的节点。新创建的节点必须有其下一个指针，指向曾经是栈顶部节点的节点：
现在我们需要一个pop方法从栈中移除顶部元素。在执行此操作时，我们还需要返回最上面的元素。如果没有更多元素，我们将使栈返回None：
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 这里要注意的是内在的陈述。如果顶部节点的next属性指向另一个节点，那么我们必须将栈顶部设置为现在指向该节点：
当栈中只有一个节点时，pop操作如下：
移除这样一个节点会导致self.top指向None：
如前所述，我们还可以添加一个peek方法。这将只返回栈的顶部，而不将其从栈中移除，从而允许我们查看顶部元素而不更改栈本身。这个操作非常简单。如果有顶层元素，则返回其数据，否则返回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 我们的函数解析传递给它的语句中的每个字符。如果它得到一个开放的括号，它会将其推到栈上。如果它得到了一个右括号，它将从栈中弹出顶部元素，并比较两个括号，以确保它们的类型匹配：（should match）、[should match]和{should match}。如果没有，我们返回False，否则继续解析。
一旦我们到了声明的结尾，我们需要做最后一次检查。如果栈为空，则我们可以返回True。但是如果栈不是空的，那么我们有一些没有匹配的结束括号的开始括号，我们将返回False。我们可以使用以下小代码测试括号匹配器：
sl = (
"{(foo)(bar)}[hello](((this)is)a)test",
"{(foo)(bar)}[hello](((this)is)atest",
"{(foo)(bar)}[hello](((this)is)a)test))"
)
for s in sl:
m = check_brackets(s)
print("{}: {}".format(s, m)) 只有三条语句中的第一条应该匹配。当我们运行代码时，我们得到以下输出：
True、False、False。代码是有效的。综上所述，栈数据结构的push和pop操作吸引了O（1）。栈数据结构很简单，但用于在现实世界中实现一系列功能。浏览器上的后退和前进按钮可以通过栈实现。为了能够在字处理器中具有撤销和重做功能，还使用了栈。
另一种特殊类型的列表是队列数据结构。这种数据结构与您在现实生活中习惯的常规队列没有什么不同。如果你在机场排队，或是在附近的商店里吃到你最喜欢的汉堡，那么你应该知道排队是怎么回事。
队列也是需要掌握的一个非常基本和重要的概念，因为许多其他数据结构都是建立在队列之上的。
队列的工作方式是，在所有条件相同的情况下，第一个加入队列的人通常首先得到服务。首字母缩略词 FIFO 最好地解释了这一点。FIFO代表先进先出。当人们站在队列中等待轮到服务时，服务只在队列的前面提供。人们离开队列的唯一时间是他们得到服务时，这只发生在队列的最前面。根据严格的定义，人们在被服务人的前面排队是违法的：
要加入队列，参与者必须先移动到队列中最后一个人的后面。队列的长度无关紧要。这是队列接受新进入者的唯一合法或允许的方式。
作为人类，我们形成的队列并不符合严格的规则。它可能会让已经排队的人决定退出，甚至让其他人代替他们。我们并不打算对真实队列中发生的所有动态进行建模。抽象什么是队列及其行为方式使我们能够解决大量的挑战，特别是在计算领域。
我们将提供队列的各种实现，但都将围绕相同的 FIFO 思想。我们将调用操作向队列中添加一个元素。要从队列中删除元素，我们将创建一个dequeue操作。每当一个元素排队时，队列的长度或大小都会增加 1。相反，出列项会将队列中的元素数减少一个。
为了演示这两种操作，下表显示了在队列中添加和删除元素的效果：
| 队列操作 | 尺寸 | 目录 | 手术结果 |
| Queue() | 0 | [] | 已创建队列对象 |
| Enqueue“标记” | 1. | ['mark'] | 添加到队列中的标记 |
| Enqueue“约翰” | 2. | ['mark','john'] | 约翰加入了队列 |
| Size() | 2. | ['mark','john'] | 返回的队列中的项目数 |
| Dequeue() | 1. | ['mark'] | 约翰退队并返回 |
| Dequeue() | 0 | [] | 标记已退出队列并返回 |
为了将到目前为止讨论的关于队列的所有内容转化为代码，让我们继续使用 Python 的list类实现一个非常简单的队列。这有助于我们快速发展并了解队列。必须在队列上执行的操作封装在ListQueue类中：
class ListQueue:
def __init__(self):
self.items = []
self.size = 0 在初始化方法__init__中，items实例变量设置为[]，表示队列创建时为空。队列的大小也设置为zero。更有趣的方法是enqueue和dequeue方法。
enqueue操作或方法使用list类的insert方法在列表前面插入项目（或数据）：
def enqueue(self, data):
self.items.insert(0, data)
self.size += 1 请注意我们是如何实现到队列末尾的插入的。索引 0 是任何列表或数组中的第一个位置。但是，在我们使用 Python 列表实现队列时，数组索引 0 是将新数据元素插入队列的唯一位置。insert操作将列表中的现有数据元素向上移动一个位置，然后将新数据插入索引 0 处创建的空间。下图显示了此过程：
为了使我们的队列反映新元素的添加，大小增加了一个：
self.size += 1 We could have used Python's shift method on the list as another way of implementing the "insert at 0". At the end of the day, an implementation is the overall objective of the exercise.
dequeue操作用于从队列中删除项目。关于队列主题的介绍，此操作捕获了我们为首先加入队列且等待时间最长的客户提供服务的点：
def dequeue(self):
data = self.items.pop()
self.size -= 1
return dataPythonlist类有一个名为pop()的方法。pop方法执行以下操作：
- 从列表中删除最后一项。
- 将从列表中删除的项返回给调用它的用户或代码。
列表中的最后一项弹出并保存在data变量中。在方法的最后一行，返回数据。
考虑下面的图中的隧道作为我们的队列。要执行一个dequeue操作，从队列前端移除数据为1的节点：
队列中的结果元素如下所示：
What can we say about the enqueue operation? It is highly inefficient in more than one way. The method has to first shift all the elements by one space. Imagine when there are 1 million elements in a list which need to be shifted around anytime a new element is being added to the queue. This will generally make the enqueue process very slow for large lists.
队列的另一个实现是使用两个栈。Pythonlist类将再次用于模拟栈：
class Queue:
def __init__(self):
self.inbound_stack = []
self.outbound_stack = [] 前面的queue类在初始化时将两个实例变量设置为空列表。这些栈将帮助我们实现队列。本例中的栈只是 Python 列表，允许我们对其调用push和pop方法。
inbound_stack仅用于存储添加到队列中的元素。无法在此栈上执行其他操作。
enqueue方法将元素添加到队列中：
def enqueue(self, data):
self.inbound_stack.append(data) 该方法很简单，只接收客户机想要附加到队列中的data。然后将该数据传递给queue类中inbound_stack的append方法。此外，使用append方法模拟push操作，将元素推到栈顶部。
对于inbound_stack上的enqueue数据，以下代码适用：
queue = Queue()
queue.enqueue(5)
queue.enqueue(6)
queue.enqueue(7)
print(queue.inbound_stack) 队列中inbound_stack的命令行输出如下：
[5, 6, 7]dequeue操作比enqueue对应操作更复杂。添加到队列中的新元素最终会出现在inbound_stack中。我们没有从inbound_stack中删除元素，而是将注意力转移到outbound_stack。正如我们所说，元素只能通过outbound_stack从我们的队列中删除：
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是否为空。如果它不是空的，我们通过执行以下操作继续删除队列前面的元素：
return self.outbound_stack.pop() 如果outbound_stack为空，则inbound_stack中的所有元素都会移动到outbound_stack中，队列中前面的元素才会弹出：
while self.inbound_stack:
self.outbound_stack.append(self.inbound_stack.pop()) 只要inbound_stack中有元素，while循环将继续执行。
语句self.inbound_stack.pop()将删除添加到inbound_stack的最新元素，并立即将弹出的数据传递给self.outbound_stack.append()方法调用。
最初，我们的inbound_stack充满了5、6和7元素：
执行while循环体后，outbound_stack如下：
dequeue方法中的最后一行将在outbound_stack上进行pop操作后返回5：
return self.outbound_stack.pop() 这使得outbound_stack只有两个元素：
下次调用dequeue操作时，while循环将不会执行，因为outbound_stack中没有元素，这使得外部if语句失败。
在这种情况下会立即调用pop操作，以便只返回队列中等待时间最长的元素。
使用此队列实现的典型代码运行如下：
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方法，之后再次打印队列时，会观察到元素数量的变化。
Implementing a queue with two stacks is a popular question posed during interviews.
使用 Python 列表实现队列是了解队列工作方式的良好开端。我们完全可以利用指针结构的知识来实现自己的队列数据结构。
队列可以使用双链表实现，并且在该数据结构上的insertion和deletion操作的时间复杂度为O（1。
node类的定义与我们在讨论双链表时定义的Node相同，如果双链表支持 FIFO 类型的数据访问，则可以将其视为队列，其中添加到列表中的第一个元素是第一个要删除的元素。
queue类与双联list类非常相似：
class Queue:
def __init__(self):
self.head = None
self.tail = None
self.count = 0 创建queue类实例时，将self.head和self.tail指针设置为None。为了对Queue中的节点数进行计数，count实例变量也在此处维护，并设置为0。
元素通过enqueue方法添加到Queue对象。本例中的元素是节点：
def enqueue(self, data):
new_node = Node(data, None, None)
if self.head is None:
self.head = new_node
self.tail = self.head
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.count += 1 enqueue方法代码与双链表append操作中已经解释的代码相同。它根据传递给它的数据创建一个节点，并将其附加到队列的尾部，或者如果队列为空，则将self.head和self.tail都指向新创建的节点。队列中的元素总数按self.count += 1.行增加
另一个使我们的双链表表现为队列的操作是dequeue方法。此方法用于删除队列前面的节点。
要删除self.head指向的第一个元素，使用if语句：
def dequeue(self):
current = self.head
if self.count == 1:
self.count -= 1
self.head = None
self.tail = None
elif self.count > 1:
self.head = self.head.next
self.head.prev = None
self.count -= 1 current通过指向self.head进行初始化。如果self.count为 1，则表示列表中只有一个节点，且始终为队列。因此，为了移除关联节点（由self.head指向），将self.head和self.tail变量设置为None。
另一方面，如果队列有多个节点，则头部指针将移动到指向self.head的下一个节点。
if语句运行后，该方法返回head指向的节点。self.count在if语句执行路径流中以任何一种方式递减一。
有了这些方法，我们成功地实现了队列，大量借鉴了双链表的思想。
还要记住，将双链表转换为队列的唯一方法是两种方法，即enqueue和dequeue。
队列用于在计算机领域实现各种功能。例如，不是为网络上的每台计算机提供自己的打印机，而是通过将每台打印机要打印的内容排队，使计算机网络共享一台打印机。当打印机准备打印时，它将选择队列中的一项（通常称为作业）进行打印。
操作系统还将 CPU 执行的进程排队。让我们创建一个应用程序，该应用程序使用队列来创建基本媒体播放器。
大多数音乐播放器软件都允许用户将歌曲添加到播放列表中。按下播放按钮后，主播放列表中的所有歌曲都会一首接一首地播放。歌曲的顺序播放可以通过队列实现，因为要排队的第一首歌曲是播放的第一首歌曲。这与 FIFO 首字母缩略词一致。我们将实现自己的播放列表队列，以 FIFO 方式播放歌曲。
基本上，我们的媒体播放器队列只允许添加曲目和播放队列中所有曲目的方式。在成熟的音乐播放器中，线程将用于改进与队列的交互方式，而音乐播放器将继续用于选择要播放、暂停甚至停止的下一首歌曲。
track课程将模拟一个音乐曲目：
from random import randint
class Track:
def __init__(self, title=None):
self.title = title
self.length = randint(5, 10) 每首曲目都包含歌曲标题和歌曲长度的参考。长度是介于 5 和 10 之间的随机数。随机模块提供randint方法，使我们能够生成随机数。该类表示任何包含音乐的 MP3 曲目或文件。曲目的随机长度用于模拟播放歌曲或曲目所需的秒数。
要创建一些曲目并打印其长度，我们将执行以下操作：
track1 = Track("white whistle")
track2 = Track("butter butter")
print(track1.length)
print(track2.length) 上述代码的输出如下所示：
6
7根据为两个轨迹生成的随机长度，您的输出可能会有所不同。
现在，让我们创建队列。使用继承，我们只是从queue类继承：
import time
class MediaPlayerQueue(Queue):
def __init__(self):
super(MediaPlayerQueue, self).__init__() 通过调用super来正确初始化队列。该类本质上是一个队列，在队列中包含许多轨迹对象。要将曲目添加到队列中，将创建一个add_track方法：
def add_track(self, track):
self.enqueue(track) 方法将一个track对象传递给队列super类的enqueue方法。实际上，这将使用track对象（作为节点的数据）创建Node，如果队列不为空，则指向尾部；如果队列为空，则指向头部和尾部。
假设队列中的曲目从添加的第一首曲目到最后一首曲目（FIFO）按顺序播放，play功能必须循环播放队列中的元素：
def play(self):
while self.count > 0:
current_track_node = self.dequeue()
print("Now playing {}".format(current_track_node.data.title))
time.sleep(current_track_node.data.length) self.count记录何时将曲目添加到我们的队列中，以及曲目何时退出队列。如果队列不是空的，对dequeue方法的调用将返回队列前面的节点（其中包含track对象）。然后，print语句通过节点的data属性访问曲目的标题。为了进一步模拟曲目的播放，time.sleep()方法暂停程序执行，直到曲目的秒数结束：
time.sleep(current_track_node.data.length) 媒体播放器队列由节点组成。将轨迹添加到队列时，轨迹将隐藏在新创建的节点中，并与该节点的数据属性关联。这解释了为什么我们通过调用dequeue返回的节点数据属性访问节点的track对象：
你可以看到，我们的node对象不是只存储任何数据，而是在本例中存储轨迹。
让我们带着音乐播放器转一圈：
track1 = Track("white whistle")
track2 = Track("butter butter")
track3 = Track("Oh black star")
track4 = Track("Watch that chicken")
track5 = Track("Don't go") 我们创建了五个以随机单词为标题的轨迹对象：
print(track1.length)
print(track2.length)
>> 8 >> 9由于随机长度的原因，输出应该与您在机器上获得的不同。
接下来，创建MediaPlayerQueue类的一个实例：
media_player = MediaPlayerQueue() 将添加曲目，play功能的输出应按照我们排队的顺序打印播放的曲目：
media_player.add_track(track1)
media_player.add_track(track2)
media_player.add_track(track3)
media_player.add_track(track4)
media_player.add_track(track5)
media_player.play() 上述代码的输出如下所示：
>>Now playing white whistle
>>Now playing butter butter
>>Now playing Oh black star
>>Now playing Watch that chicken
>>Now playing Don't go在执行程序时，可以看到曲目是按照队列的顺序播放的。播放曲目时，系统还会暂停与曲目长度相等的秒数。
在本章中，我们使用了将节点链接在一起的知识来创建其他数据结构，即栈和队列。我们已经看到了这些数据结构是如何紧密模拟现实世界中的栈和队列的。已经展示了具体的实现及其不同的类型。我们后来应用栈和队列的概念来编写现实生活中的程序。
我们将在下一章考虑树木。将讨论树上的主要操作，以及应用数据结构的不同领域。