你好，我是悦创。

1. 故事背景

1.1 人物：

大牛、小白

1.2 场景：

高铁中 ‘牛与白’ 的深入交流

1.3 前言：

栈和队列是计算机科学中使用的比较广泛的两种数据结构，如：程序的递归是使用栈来实现的，操作系统中进程调度网络管理中的打印服务等都是通过队列来实现的。

“啤酒饮料矿泉水，花生瓜子火腿肠。来，腿收一下了啊~”

“列车模型，有需要的乘客吗？列车模型，有需要的乘客吗？”

“这无聊的旅途，相信大家都辛苦了，接下来我给大家带来一个有意思的产品…”

“牛哥，要不然咱们改行来高铁上卖东西吧，看看看看，前边那个小伙子又花钱了。这钱也太好赚了。”

“好啊，你来高铁上开店，我给你赞助。多了没有，三五十还是能投资得起的。”

“在公司就知道你牛哥抠门，没想到出来一趟还是这么抠。哎，我是上了贼船下不去咯。”

“还敢说我抠门，刚才的水白让你喝了是吧？”

“哈哈哈哈哈哈……”小白笑的前仰后翻。“牛哥，你不说还好，你这一说，都能把我笑死，你见谁出个差，灌两瓶自来水带着喝。”

大牛老脸一红，说道：“不说这个不说这个，上次我让你好好学学数据结构和算法，有什么成果没有？”

您这么一说啊，我这儿正好有个问题需要请教您一下。

听到大牛问他成果，小白也收起了玩笑的表情。认真的说道。

你小子今天怎么这么谦虚呢，有古怪哈。那你先说说，有什么问题能难住你。

我现在不是学到队列了嘛。有点儿不明白栈和队列有什么不一样，他们两个都是线性存储方式，也都有增删功能。我看没什么不一样的。

你这专业成绩不是挺好的吗，怎么连这个都不知道？

每个人都有自己的长处和短处嘛，这个方面我就特别的薄弱，还请牛哥不吝赐教。

看你这么诚恳的份儿上。就让老夫好好和你说说。

先来说一下他们两个的定义：

• 栈和队列都是受限的线性表。

什么叫受限呢？
意思是说他们的增删功能是受到系统限制的。只能在固定的地方删除或者添加元素，不能任意增删其他位置的元素。

1.4 栈

1. 又叫堆栈
2. 受限操作：限定只能在表尾进行增加和删除操作。可进行操作的一端成为 栈顶 。不可操作的一端成为 栈底 。
3. 增加元素的操作又称为进栈、入栈或者压栈。意思是把元素添加到栈顶的位置。
4. 删除元素的操作又称为出栈或者退栈。意思是把元素从栈顶移除。使其相邻元素成为栈顶元素。

1.5 队列

1. 受限操作：限定只能在表的前端进行删除操作，只能在表的后端进行插入操作。
2. 进行插入操作的一端称为队尾，进行删除操作的一端称为队头。
3. 增加元素的操作称为入队列 ，意思是把元素添加到队尾的位置。
4. 删除元素的操作称为出队列 ，意思是把元素从队头位置移除。

这个我知道的牛哥，我问的是有什么不一样。

就你懂得多是吧，我这不是还没说到呢吗，你着急什么。大牛白了一眼小白，然后继续说到。

栈和队列最大的不同点是元素增删的顺序。栈为 先入后出 ，队列为 先入先出 。

2. 栈

1. 把一个水杯比作一个栈结构；
2. 将水倒入水杯的过程就是水入栈的过程；
3. 喝水的时候就是水出栈的过程。结论：最先被我们倒入杯中的水肯定会最后被我们喝到。 — 先入后出

上面我们是娱乐性解析了：栈，接下来专业并且认真一点吧！

栈有时也被称作“下推栈”。它是有序集合，添加操作和移除操作总发生在同一端，即“顶 端”，另一端则被称为“底端”。

栈中的元素离底端越近，代表其在栈中的时间越长，因此栈的底端具有非常重要的意义。最新添加的元素将被最先移除。这种排序原则被称作 LIFO（last-in first-out），即后进先出。

• 它提供了一种基于在集合中的时间来排序的方式。
• 最近添加的元素靠近顶端，旧元素则靠近底端。

栈的例子在日常生活中比比皆是。几乎所有咖啡馆都有一个：由托盘或盘子构成的栈，你可以从顶部取走一个，下一个顾客则会取走下面的托盘或盘子。

图 3-1 是由书构成的栈，唯一露出封面的书就是顶部的那本。为了拿到其他某本书，需要移除压在其上面的书。图 3-2 展示了另一个栈，它包含一些原生的 Python 数据对象。

图3-1 由书构成的栈

图3-2 由原生的 Python 数据对象构成的栈

观察元素的添加顺序和移除顺序，就能理解栈的重要思想。

假设桌面一开始是空的，每次只往桌上放一本书。如此堆叠，便能构建出一个栈。取书的顺序正好与放书的顺序相反。

由于可用于反转元素的排列顺序，因此栈十分重要。元素的插入顺序正好与移除顺序相反。图 3-3 展示了 Python 数据对象栈的创建过程和拆除过程。请仔细观察数据对象的顺序。

考虑到栈的反转特性，我们可以想到在使用计算机时的一些例子。例如，每一个浏览器都有返回按钮。当我们从一个网页跳转到另一个网页时，这些网页——实际上是 URL——都被存放在一个栈中。

当前正在浏览的网页位于栈的顶端，最早浏览的网页则位于底端。如果点击返回按钮，便开始反向浏览这些网页。

2.1 栈抽象数据类型

栈抽象数据类型由下面的结构和操作定义。

如前所述，栈是元素的有序集合，添加操作与移除操作都发生在其顶端。

栈的操作顺序是 LIFO，它支持以下操作。

• Stack()：创建一个空栈。它不需要参数，且会返回一个空栈。
• push(item)：将一个元素添加到栈的顶端。它需要一个参数 item，且无返回值。
• pop()：将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容。
• peek()：返回栈顶端的元素，但是并不移除该元素。它不需要参数，也不会修改栈的内容。
• isEmpty()：检查栈是否为空。它不需要参数，且会返回一个布尔值。
• size()： 返回栈中元素的数目。它不需要参数，且会返回一个整数。

假设 s 是一个新创建的空栈。下表展示了对 s 进行一系列操作的结果。在“栈内容”一列 中，栈顶端的元素位于最右侧：

2.2 用 Python 实现栈

明确定义栈抽象数据类型之后，我们开始用 Python 来将其实现。如前文所述，抽象数据类型的实现常被称为数据结构。

和其他面向对象编程语言一样，每当需要在 Python 中实现像栈这样的抽象数据类型时，就可以创建新类。栈的操作通过方法实现。更进一步地说，因为栈是元素的集合， 所以完全可以利用 Python 提供的强大、简单的原生集合来实现。这里，我们将使用列表。

Python 列表是有序集合，它提供了一整套方法。举例来说，对于列表 [2, 5, 3, 6, 7, 4]， 只需要考虑将它的哪一边视为栈的顶端。一旦确定了顶端，所有的操作就可以利用 append 和 pop 等列表方法来实现。

下面的代码，是栈的实现，它假设列表的尾部是栈的顶端。当栈增长时（即进行 push 操作）， 新的元素会被添加到列表的尾部。pop 操作同样会修改这一端。

class Stack(object):
    """栈
    Stack() 创建一个空栈。它不需要参数，且会返回一个空栈。
    push(item) 将一个元素添加到栈的顶端。它需要一个参数 item，且无返回值。
    pop() 将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容。
    peek() 返回栈顶端的元素，但是并不移除该元素。它不需要参数，也不会修改栈的内容。
    is_empty() 检查栈是否为空。它不需要参数，且会返回一个布尔值。
    size() 返回栈中元素的数目。它不需要参数，且会返回一个整数。
    """
    def __init__(self):
        self.items = []
    def isEmpty(self):
        """判断是否为空"""
        return self.items == []
    def push(self, item):
        """加入元素"""
        self.items.append(item)
    def pop(self):
        """弹出元素"""
        return self.items.pop()
    def peek(self):
        """返回栈顶元素"""
        return self.items[len(self.items) - 1]
    def size(self):
        """返回栈的大小"""
        return len(self.items)
if __name__ == "__main__":
    stack = Stack()
    stack.push("hello")
    stack.push("world")
    stack.push("aiyc")
    print(stack.size())
    print(stack.peek())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

In [2]: s = Stack()

In [3]: s.isEmpty()
Out[3]: True

In [4]: s.push(4)

In [5]: s.push('dog')

In [6]: s.peek()
Out[6]: 'dog'

In [7]: s.push(True)

In [8]: s.size()
Out[8]: 3

In [9]: s.isEmpty()
Out[9]: False

In [10]: s.push(8.4)

In [11]: s.pop()
Out[11]: 8.4

In [12]: s.pop()
Out[12]: True

In [13]: s.size()
Out[13]: 2

值得注意的是，也可以选择将列表的头部作为栈的顶端。不过在这种情况下，便无法直接使用 pop 方法和 append 方法，而必须要用 pop 方法和 insert 方法显式地访问下标为 0 的元素， 即列表中的第 1 个元素。

2.3 栈的另一种实现

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

    def isEmpty(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)

改变抽象数据类型的实现却保留其逻辑特征，这种能力体现了抽象思想。

不过，尽管上述两 种实现都可行，但是二者在性能方面肯定有差异。

append 方法和 pop()方法的时间复杂度都是 O(1) ，这意味着不论栈中有多少个元素，第一种实现中的 push 操作和 pop 操作都会在恒定的时间内完成。

第二种实现的性能则受制于栈中的元素个数，这是因为 insert(0) 和 pop(0) 的时间复杂度都是 O(n) ，元素越多就越慢。显而易见，尽管两种实现在逻辑上是相等的，但是它们在 进行基准测试时耗费的时间会有很大的差异。

3. 队列

1. 把银行叫号流程看做一个队列；
2. 用户拿号 — 入队列；
3. 客服人员叫号 — 出队列。结论：最先拿到号的客户肯定被首先叫到号 — 先入先出

接下来学习另一个线性数据结构：队列。与栈类似，队列本身十分简单，却能用来解决众多重要问题。

3.1 何谓队列

队列是有序集合，添加操作发生在“尾部”，移除操作则发生在“头部”。新元素从尾部进入 队列，然后一直向前移动到头部，直到成为下一个被移除的元素。

最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素则排在最前面。这种排序 原则被称作 FIFO（first-in first-out），即先进先出，也称先到先得。

在日常生活中，我们经常排队，这便是最简单的队列例子。进电影院要排队，在超市结账要 排队，买咖啡也要排队（等着从盘子栈中取盘子）。好的队列只允许一头进，另一头出，不可能 发生插队或者中途离开的情况。下图展示了一个由 Python 数据对象组成的简单队列。

计算机科学中也有众多的队列例子。

我的计算机实验室有 30 台计算机，它们都与同一台打印机相连。当学生需要打印的时候，他们的打印任务会进入一个队列。该队列中的第一个任务就是即将执行的打印任务。

如果一个任务排在队列的最后面，那么它必须等到前面的任务都执行完毕后才能执行。我们稍后会更深入地探讨这个有趣的例子。

操作系统使用一些队列来控制计算机进程。调度机制往往基于一个队列算法，其目标是尽可能快地执行程序，同时服务尽可能多的用户。在打字时，我们有时会发现字符出现的速度比击键 速度慢。这是由于计算机正在做其他的工作。击键操作被放入一个类似于队列的缓冲区，以便对应的字符按正确的顺序显示。

3.2 队列抽象数据类型

class Queue(object):
    """队列"""
    def __init__(self):
        self.items = []

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

    def enqueue(self, item):
        """进队列"""
        self.items.insert(0,item)

    def dequeue(self):
        """出队列"""
        return self.items.pop()

    def size(self):
        """返回大小"""
        return len(self.items)

if __name__ == "__main__":
    q = Queue()
    q.enqueue("hello")
    q.enqueue("world")
    q.enqueue("itcast")
    print(q.size())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

这里我只是用列表方式分别实现了栈和队列，当然也可以使用其他方式，如：对象。链表等。剩下的方式你可以自己试一下，我就不多写了。

好好好，等咱们到了地方我就自己着手实现一次。加深加深印象。不不不，我现在就实现一次。“说这小白从包里拿出来笔记本，‘啪啪啪……’ 的就开始敲代码。