JavaScript 数据结构（2-1）：栈与队列-栈篇

翻译：疯狂的技术宅 说明：本文翻译自系列文章《Data Structures With JavaScript》，总共为四篇，原作者是在美国硅谷工作的工程师 Cho S. Kim 。由京程一灯老编 疯狂的技术宅 翻译。今天为大家奉上本系列的第二篇。由于第二篇内容过多，这次先推送上半部分——栈。 英文：https://code.tutsplus.com/articles/data-structures-with-javascript-stack-and-queue--cms-23348

栈和队列是web开发中最常用的两种数据结构。绝大多数用户，甚至包括web开发人员，都不知道这个惊人的事实。如果你是一个程序员，那么请听我讲两个启发性的例子：使用栈来组织数据，来实现文本编辑器的“撤消”操作；使用队列处理数据，实现web浏览器的事件循环处理事件（单击click、悬停hoover等）。

等等，先想象一下作为用户和程序员，我们每天使用栈和队列的次数，这太惊人了吧！由于它们在设计上有普遍性和相似性，我决定从这里开始为大家介绍数据结构。

栈

在计算机科学中，栈是一种线性数据结构。如果你理解起来有困难，就像最初的我一样非常困惑，不妨这样认为：一个栈可以对数据按照顺序进行组织和管理。

要理解这种顺序，我们可以把栈这种结构想象为自助餐厅的一堆盘子，当一个盘子被叠加到一堆盘子上时，原有的盘子保留了它们原来的顺序；同时，当一个新盘子被添加时，它会朝栈的底部方向堆积。每当我们添加一个新盘子时，被称作入栈，这个新盘子处于栈的顶部，也被称作栈顶。

这个过程会保留每个盘子被添加到栈中的顺序，每次从栈中取出一个盘子时也是一样的。

我可能用了太多的篇幅来描述自助餐厅中的盘子是怎样被添加和删除的过程。这样做是为了让大家理解栈更多的技术细节，让我们回顾一下前面关于文本编辑器的“撤消”操作。每次将文本添加到文本编辑器事，该文本被压入栈中。其中第一次添加的文本代表栈的底部（栈底）；最后一次的修改表示栈的顶部（栈顶）。如果用户希望撤销最后一次修改，则删除处于栈顶部的那段文本，这个过程可以不断重复，一直到栈中没有更多内容，这时我们会得到一个空白文件。

栈的操作

现在我们对栈的模型有了基本概念，下一步就要定义栈的两个操作：

• push(data) 添加数据
• pop() 删除最后添加的数据

栈的实现

现在让我们开始为栈编写代码吧！

栈的属性

为了实现栈结构，我们将会创建一个名为 Stack 的构造函数。栈的每个实例都有两个属性：_size 和 _storage。

function Stack() {    this._size = 0;    this._storage = {};}

this._storage 属性使栈的每一个实例都具有自己的用来存储数据的容器； this._size 属性反映了当前栈中数据的个数。如果创建了一个新的栈的实例，并且有一个数据被存入栈中，那么 this._size 的值将被增加到1。如果又有数据入栈，this._size 的值将增加到2。如果一个数据从栈中被取出，this._size 的值将会减少为1。

栈的方法(操作)

我们需要定义可以向栈中添加（入栈）和从栈中取出（出栈）数据的方法。先从添加数据开始。

方法1/2: push(data)

（每一个栈的实例都具有这个方法，所以我们把它添加到栈结构的原型中）

我们对这个方法有两个要求：

1. 每当添加数据时，希望能够增加栈的大小。
2. 每当添加数据时，希望能够保留它的添加顺序。

Stack.prototype.push = function(data) {    // increases the size of our storage    var size = this._size++;    // assigns size as a key of storage    // assigns data as the value of this key    this._storage[size] = data;};

在实现push(data)方法时要包含以下逻辑：声明一个变量 size 并赋值为 this._size++。指定 size 为 this._storage 的键；并将数据赋给相应键的值。

如果我们调用push(data)方法5次，那么栈的大小将是5。第一次入栈时，将会把数据存入 this._storage 中键名为1对应的空间，当第5次入栈时，将会把数据存入this._storage 中键名为5对应的空间。现在我们的数据有了顺序！

方法2/2: pop( )

前面已经实现了把数据送入栈中，下一步我们要从栈中弹出（删除）数据。从栈中弹出数据并不是简单的删除数据，它只删除最后一次添加的数据。

以下是这个方法的要点： 1. 使用栈当前的大小获得最后一次添加的数据。 2. 删除最后一次添加的数据。 3. 使 _this._size 计数减1。 4. 返回刚刚删除的数据。

Stack.prototype.pop = function() {    var size = this._size,        deletedData;    deletedData = this._storage[size];    delete this._storage[size];    this.size--;    return deletedData;};

pop( )方法满足以上四个要点。首先，我们声明了两个变量：size 用来初始化栈的大小；deletedData 用来保存栈中最后一次添加的数据。第二，我们删除了最后一次添加的数据的键值对。第三，我们把栈的大小减少了1。第四，返回从栈中删除的数据。

如果我们测试当前实现的pop( )方法，可以使用下面的用例：如果向栈内push数据，栈的大小会增加1，如果从栈中pop( )数据，栈的大小会减少1！

为了处理这个用例，我们将向pop()中添加if语句。

Stack.prototype.pop = function() {    var size = this._size,        deletedData;    if (size) {        deletedData = this._storage[size];        delete this._storage[size];        this._size--;        return deletedData;    }};

通过添加if语句，可以使代码主逻辑在存储中有数据时才被执行。

栈的完整实现

我们已经实现了完整的栈结构。不管以怎样的顺序调用任何一个方法，代码都可以工作！下面使代码的最终版本：

function Stack() {    this._size = 0;    this._storage = {};}Stack.prototype.push = function(data) {    var size = ++this._size;    this._storage[size] = data;};Stack.prototype.pop = function() {    var size = this._size,        deletedData;    if (size) {        deletedData = this._storage[size];        delete this._storage[size];        this._size--;        return deletedData;    }};

从栈到队列

当我们想要按顺序添加数据或删除数据时，可以使用栈结构。根据它的定义，栈可以只删除最近添加的数据。如果想要删除最古老的数据该怎么办呢?这时我们希望使用名为queue的数据结构。

请等待 《JavaScript 数据结构（2-2）：栈与队列-队列篇》