TypeScript版算法与数据结构-栈

JayChen 发布于2019-08-26 18:36 / 1805人阅读

摘要：时间复杂度是出栈在有之前数组的基础上，出栈也非常简单，实际上的底层操作就是删除数组中的最后一个元素，并返回该元素。出栈也是一个时间复杂度为的操作更多相关数据结构，可以前往我的。

本文的源码在这里，可以参考一下

栈也是一种使用非常广泛的线性数据结构，它具有后进先出last in first out的特点。就像我们平时一本一本的往桌上放书，等到我们又想用书时，我们首先接触到的总是我们最后一本放上去的书。
栈的添加和删除操作总是在栈的一端完成，这一端被称为栈顶，对于栈的实现，我会采用上一篇中实现的数组作为底层的数据结构，所有栈的操作都会在这个底层的数组中完成。栈的主要操作有两个，一个是入栈，一个是出栈
首先我们会定义一个TypeScript接口，这个接口会包含基础的栈这个类的实现

interface Stack {
    getSize(): number; // 获取栈中元素的个数
    isEmpty(): boolean; // 判断栈是否为空
    push(e: E): void; // 入栈一个元素
    pop(): E; // 出栈一个元素
    peek(): E; // 查看栈顶元素
}

再来看看我们类的实例属性和构造函数，其中MyArray就是上一篇中实现的数组，初始状态下，我们依然会给栈一个初始的容量10。

class ArrayStack implements Stack {
    private array: MyArray;
    constructor(capacity: number = 10) {
        this.array = new MyArray(capacity);
    }
}

1.入栈

在有之前数组的基础上，入栈也是一个非常简单的过程，实际上底层的操作就是往数组的末尾添加一个元素。时间复杂度是O(1)

public push(e: E): void {
    this.array.addLast(e);
}

2.出栈

在有之前数组的基础上，出栈也非常简单，实际上的底层操作就是删除数组中的最后一个元素，并返回该元素。出栈也是一个时间复杂度为O(1)的操作

public pop(): E {
    return this.array.removeLast();
}

更多相关数据结构，可以前往我的github。持续更新中，喜欢的话给个star~相关的问题也可以提issue，看到后会第一时间回复

GPU云服务器云服务器 c语言版数据结构栈算法与数据结构数据结构与算法数据结构与算法教程

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

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

前端每周清单第 45 期: Safari 支持 Service Worker, Parcel 完整教

摘要：的另一个核心特性，苹果表示也正在开发中，按开发进度可能几个月后就能与我们见面。是基于的本地化数据库，支持以及浏览器环境。前端每周清单专注前端领域内容，以对外文资料的搜集为主，帮助开发者了解一周前端热点；分为新闻热点、开发教程、工程实践、深度阅读、开源项目、巅峰人生等栏目。欢迎关注【前端之巅】微信公众号（ID: frontshow），及时获取前端每周清单。本期是 2017 年的最后一...

赵春朋 2019-08-21 18:24 评论0 收藏0
前端每周清单第 43 期：2017 JavaScript 回顾、Rust 与 WebAssembly

摘要：杨冀龙是安全焦点民间白帽黑客组织核心成员，被浪潮之巅评为中国新一代黑客领军人物之一他在本文中依次分享了对于黑客的定义如何从黑客成为一名安全创业者技术创业踩过的坑给技术创业者建议等内容。 showImg(https://segmentfault.com/img/remote/1460000012377230?w=1240&h=796); 前端每周清单专注前端领域内容，以对外文资料的搜集为...

xorpay 2019-08-22 11:15 评论0 收藏0
使用TypeScript和Canvas编写移动端贪吃蛇大作战游戏

摘要：基本介绍一款移动端贪吃蛇大作战游戏。主要的游戏逻辑有贪吃蛇移动碰撞检测贪吃蛇碰撞碰撞墙壁和吃食物。贪吃蛇的身体如何跟随头部移动需要分为两种情况，在单位时间内贪吃蛇移动一单位长度和贪吃蛇移动多单位长度。基本介绍一款移动端贪吃蛇大作战游戏。(只支持移动端) 这是一个临近 deadline 的课设项目，为了方便地使用TS，我直接使用angular-cli生成了TypeScript的项...

AlphaWallet 2019-08-22 15:31 评论0 收藏0
前端小报 - 201901 月刊

摘要：月日，官方团队在中宣布将对进行重大更改，主要包括将代码库从移植到，不再支持和，并为新增了一些功能等，这个更改项目代号为，目的是增强优势，弥补弱势。调查结果显示在年度荣获最受欢迎的编程语言。订阅 / 投稿：https://github.com/txd-team/monthly本期小编：x-cold (尹挚) 新闻快报重磅消息：Github 宣布私有仓库免费，同期还上线了星标话题 (...

soasme 2019-08-23 15:06 评论0 收藏0