TypeScript 旅途6:泛型,设计一个栈结构

TypeScript中的泛型功能非常强大,本节使用泛型来实现常见的数据结构:栈(Stack)。

栈的简介

栈的特点

栈(Stack)是一种线性存储结构,它具有如下特点:

栈中的数据元素遵守先进后出(First In Last Out)的原则,简称FILO结构。

只能在栈顶进行插入和删除操作。

栈的相关概念

栈顶与栈底:允许元素插入与删除的一端称为栈顶,另一端称为栈底。

入栈:从栈顶添加元素。

出栈:从栈顶删除元素。

假设我们对栈中添加三个元素,这个操作看起来像是这个样子的(图片来源与网络,非常直观)。

出栈的顺序则正好相反。

这个操作过程让我想起了汉诺塔游戏。

栈的操作

入栈

出栈

栈的元素个数

栈是否为空

选择一种数据结构作为栈的存储结构

既然是一种线性存储结构,那么可以用数组或链表来实现。单向链表应该是最简单的一种方式,本篇使用单向链表来实现。

栈的实现方式

定义一个接口,明确栈有哪些功能

定义栈中存储的元素

每个元素有一个T类型的值,和一个next的引用,指向下一个元素。

使用单向链表实现的栈,操作起来应该是下面这个样子。

入栈与出栈都是在栈顶一端来完成的。

使用泛型类实现栈

使用单向链表实现栈非常简单。定义一个_size变量记录栈中的元素数量,并在入栈与出栈的时候做相应的修改。再定义一个_header元素,它的next是指向栈顶的元素,在出栈与入栈中对它的next做相应的调整。

测试用例

实现完成后当然要使用不同的数据类型来测试下是不是预期的效果。

成功的信念在人脑中的作用就如闹钟,会在你需要时将你唤醒。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180201G05BD400?refer=cp_1026

同媒体快讯

扫码关注云+社区