JavaScript数据结构02 - 栈

legendaryedu 发布于2019-08-23 10:22 / 1759人阅读

摘要：它们就是栈和队列。概念栈是一种遵循后进先出原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。栈也被用在编程语言的编译器和内存中保存变量方法调用等，比如函数的调用栈。

一、定义 1.1 背景

通过前面一节《JavaScript数据结构01 - 数组》我们知道，可以在数组的任意位置上删除或添加元素。然而，有时候我们还需要一种在添加或删除元素时有更多控制的数据结构。

有两种数据结构类似于数组，但在添加和删除元素时更为可控。

它们就是栈和队列。

1.2 概念

栈是一种遵循后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。

在栈里，新元素都靠近栈顶，旧元素都接近栈底。

栈也被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈。

二、栈的实现 2.1 创建一个类来表示栈

这里我还是用构造函数的形式来书写，大家有兴趣可以用ES6的Class来重写一遍。

// Stack类
function Stack () {
  this.items = [];

  this.push = push;
  this.pop = pop;
  this.peek = peek;
  this.isEmpty = isEmpty;
  this.clear = clear;
  this.size = size;
  this.print = print;
}

栈里面有一些声明的方法：

push(element)：添加一个（或几个）新元素到栈顶

pop()：移除栈顶的元素，同时返回被移除的元素

peek()：返回栈顶的元素，不对栈做任何修改

isEmpty()：如果栈里没有任何元素就返回true，否则返回false

clear()：移除栈里的所有元素

size()：返回栈里的元素个数

2.2 实现栈中的辅助方法

// 添加新元素到栈顶
function push (element) {
  this.items.push(element);
}

// 移除栈顶元素，同时返回被移除的元素
function pop () {
  return this.items.pop();
}

// 查看栈顶元素
function peek () {
  return this.items[this.items.length - 1];
}

// 判断是否为空栈
function isEmpty () {
  return this.items.length === 0;
}

// 清空栈
function clear () {
  this.items = [];
}

// 查询栈的长度
function size () {
  return this.items.length;
}

// 打印栈里的元素
function print () {
  console.log(this.items.toString());
}

2.3 创建实例进行测试

// 创建Stack实例
var stack = new Stack();

console.log(stack.isEmpty());     // true
stack.push(5);                    // undefined
stack.push(8);                    // undefined
console.log(stack.peek());        // 8
stack.push(11);                   // undefined
console.log(stack.size());        // 3
console.log(stack.isEmpty());     // false
stack.push(15);                   // undefined
stack.pop();                      // 15
console.log(stack.size());        // 3
stack.print();                    // 5,8,11
stack.clear();                    // undefined
console.log(stack.size());        // 0

三、结束

本文会同步到我的个人博客，完整代码可以到我的github仓库查看，如果对你有帮助的话欢迎点一个Star~~

欢迎关注我的公众号

GPU云服务器云服务器 javascript全栈视频 javascript全栈教程 javascript全栈开发 javascript快速全栈开发

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96283.html

Day02 - JavaScript + CSS Clock

摘要：作者简介是推出的一个天挑战。完整指南在从零到壹全栈部落。通过时分秒对一圈度，进行映射，确定每一个指针所需旋转的角度。此前的代码中，每秒都会重新一个对象，用来计算角度值，但如果让这个角度值一直保持增长，也就不会出现逆时针回旋的问题了。 Day02 - JavaScript + CSS Clock 作者：©liyuechun 简介：JavaScript30 是 Wes Bos 推出的一个...

zzbo 2019-08-20 18:07 评论0 收藏0
前端基础进阶（一）：内存空间详细图解

摘要：一栈数据结构与不同，中并没有严格意义上区分栈内存与堆内存。引用数据类型的值是保存在堆内存中的对象。不允许直接访问堆内存中的位置，因此我们不能直接操作对象的堆内存空间。为了更好的搞懂变量对象与堆内存，我们可以结合以下例子与图解进行理解。 showImg(https://segmentfault.com/img/remote/1460000009784102?w=1240&h=683); ...

_Suqin 2019-08-21 18:30 评论0 收藏0
【Step-By-Step】一周面试题深入解析 / 周刊02

摘要：关于点击进入项目是我于开始的一个项目，每个工作日发布一道面试题。即使这个时间周期内，小明取得多次满分。创建作用域链在执行期上下文的创建阶段，作用域链是在变量对象之后创建的。这种一层一层的关系，就是作用域链。关于【Step-By-Step】 Step-By-Step (点击进入项目) 是我于 2019-05-20 开始的一个项目，每个工作日发布一道面试题。每个周末我会仔细阅读大家的答...

ixlei 2019-08-30 11:04 评论0 收藏0
【Step-By-Step】一周面试题深入解析 / 周刊02

摘要：关于点击进入项目是我于开始的一个项目，每个工作日发布一道面试题。即使这个时间周期内，小明取得多次满分。创建作用域链在执行期上下文的创建阶段，作用域链是在变量对象之后创建的。这种一层一层的关系，就是作用域链。关于【Step-By-Step】 Step-By-Step (点击进入项目) 是我于 2019-05-20 开始的一个项目，每个工作日发布一道面试题。每个周末我会仔细阅读大家的答...

BDEEFE 2019-08-23 17:55 评论0 收藏0
2017-07-02 前端日报

摘要：前端日报精选译，和的未来学习笔记箭头函数学习笔记教程栅格布局卷土重来，用还是为什么我会选择而不是众成翻译原生开发入门完全教程从零到壹全栈部落中文一个端带文件路径和颜色的攻城方略译使用提高应用程序的种方式中自定义操作符修仙 2017-07-02 前端日报精选 [译] TC39，ECMAScript 和 JavaScript 的未来（Part 1）ES6学习笔记：箭头函数_ES6, Ja...

lemon 2019-08-20 17:42 评论0 收藏0