背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

用栈和队列打造优雅的代码

栈

栈和数组存储数据的方式一样，它们都只是元素的列表。不同之处在于栈的以下3个限制。

• 数据只能从栈末插入。
• 数据只能从栈末删除。
• 只能读取栈的最后一个元素。

大多数计算机科学的文献会把栈的末尾称为栈顶，而把栈的开头称为栈尾。

向栈插入新值也称为压栈。

从栈顶移除元素称为出栈。因为栈的限制，所以只能从栈顶弹出数据。

压栈和出栈操作可以用LIFO形容，也就是“后进先出”（last in, first out）。最后一个压入栈的元素同时也是第一个被弹出的。

抽象数据类型

大多数编程语言的内置数据类型或者类中没有栈，你需要自行实现。

要创建一个栈，一般需要用某种内置数据结构来实际存储数据。下面是栈的一种使用数组的Ruby实现：

class Stack
  def initialize
    @data = []
  end
  def push(element)
    @data << element
  end
  def pop
    @data.pop
  end
  def read
    @data.last
  end
end

这个实现在一个名为@data的数组中存储数据。

实例化栈的时候，会自动建立一个空数组@data = []。这个栈会使用push方法向@data数组插入元素，使用pop方法从@data数组移除元素，使用read方法从@data数组读取元素。

但这样使用数组构建Stack类，该接口就会强制用户只能用有限方式访问数组。正常情况下，我们可以读取数组的任意索引。但通过栈接口使用数组就只能读取最后一个元素。插入数据和删除数据也是如此。

因此栈和数组并不是同类数据结构。数组可以直接访问计算机内存，并且内置于大多数编程语言中。而栈其实是限制访问数组的一组规则和过程，它让我们只能获得特定结果。

事实上，用什么数据结构来实现栈根本不重要。只要有一组数据以LIFO方式操作就足够了。至于使用数组还是其他内置数据结构来实现栈都无所谓。因此，栈属于所谓的抽象数据结构——也就是围绕其他内置数据结构构建的一组理论规则。

有一点需要指出：即便是内置数据结构也可能是抽象数据结构。即便某种编程语言实现了Stack类，栈仍然是一种概念，可以用不同数据结构实现。

队列

队列是另一种处理临时数据的数据结构。队列和栈在很多方面很相近，但二者处理数据的顺序不同。和栈一样，队列也是抽象数据结构。

第一个添加到队列中的元素也是第一个被移除的。这就是计算机科学家使用“FIFO”这一术语的原因：先进先出（first in, first out）。

队列的开头被称为前端，而结尾被称为后端。

和栈一样，队列也是有3条限制（与栈的限制不同）的数组。

• 数据只能插入队列末尾（与栈一样）。
• 只能从队列前端删除数据（与栈相反）。
• 只能读取队列前端的数据（与栈相反）。

队列实现

前面讲过，队列是抽象数据结构。和许多其他抽象数据结构一样，大部分编程语言没有默认实现队列。下面是队列的一个Ruby实现：

class Queue
  def initialize
    @data = []
  end
  def enqueue(element)
    @data << element
  end
  def dequeue
    # Ruby的shift方法会移除并返回数组的第一个元素：
    @data.shift
  end
  def read
    @data.first
  end
end

和栈一样，Queue类也用一个限制数据操作的接口包装了数组。我们只能用特定方式处理数据。enqueue方法可以向数组末尾插入数据，而dequeue方法则会移除数组的第一个元素。read方法让我们可以读取数组的第一个元素。

总结

栈和队列本质上都是数组。

具体来说，栈和队列是处理临时数据的优雅方法。无论是操作系统架构，还是打印队列，抑或是遍历数据，都可以使用栈和队列作为临时容器，写出漂亮的算法。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。