数据结构Stack

​ 在很多应用中,我们需要维护多个对象的集合,这种操作非常简单。我们可能想要向集合中 加入某个元素,去掉某个元素,以及遍历 集合中的元素并对他们执行某种操作,当然还有 检查集合是否为空。对于大多数操作来说,目的都很明确 关键是当需要去掉一个元素时,去掉哪一个元素呢?处理这类问题 有两个经典基础数据结构,栈和队列。

​ 它们的区别就在于 去除元素的选择方式。在栈中,我们取出 最近加入的元素。插入元素对应的术语是入栈(push) 去掉最近加入的元素叫做出栈(pop)。这也叫做后进先出原则 ( LIFO )。在队列中,我们关注最先加入队列的元素 为了和栈的操作区分,队列加入元素的操作叫做入队(enqueue) 去除元素的操作叫做出队(dequeue)。这也叫做先入先出原则 (FIFO)

​ 如何实现这些操作 ,我们今天隐含的主题是模块式编程。这也将是我们需要特别遵守的原则,这一原则主要思想是将接口与实现完全分离,比如我们精确定义了一些如栈、队列等数据结构的时候和数据类型,我们想要的是实现的细节与客户端的 完全分离。客户端可以选择不同的实现 但是客户端代码只能执行基本操作 另一方面,实现部分无法知道客户端需求的细节 它所要做的只是实现这些操作 这样,很多客户端能够共用同一个实现 这使得我们能够用模块式可复用的算法与数据结构库 来构建更复杂的算法和数据结构。在 Java 这门语言中就是使用接口俩统一 API,我们的所有实现必须遵从我们先前的 API。

​ 现在,我们来看实现栈的代码 我们要看的第一个实现使用链表。

package Stack;

public class StacksLink {

    private class Node{
        String item;
        Node next;
    }

    private Node first = null;

    public boolean isEmpty(){
        return first == null;
    }

    public void push(String item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
    }

    public String pop(){
        Node temp = first;
        first = first.next;
        return temp.item;
    }
}

​ 好,我们来看代码 这门课中所有的链式数据结构中 我们使用Java中内部类来实现,这只是 描述我们要操作的节点对象的一种方法 节点对象由一个字符串和指向另一个节点的引用组成。

​ 所以,链表的 出栈操作非常容易实现。首先,我们需要 返回链表中第一个元素,所以先将它存在变量item中 然后,要去掉第一个节点,我们只需要将 链表指向第一个元素的指针指向下一个元素 然后第一个节点就等着被垃圾回收处理 最后,返回保存的元素。

​ 入栈操作呢? 我们要在链表头加入新的节点 首先,将指向链表头的指针存起来,oldfirst = first 然后创建新节点,这是我们要插入链表头 的新节点。first = new Node() 这是个实例变量,它的元素就是我们想要插入链表头 的字符串,这个例子中是“not”,它的next指针指向链表oldfirst元素 现在成了链表第二个元素。在这个操作之后 first指向链表头处的元素,链表中的元素依照 入栈时间降序排列。实现入栈操作 只需要四行代码。

​ 这个类中构造函数不做任何操作 也就不用写构造函数。内部类用来构成链表中的元素 将它写成了内部类,这样我们能够直接访问这些实例变量 栈唯一的实例变量是 链表中第一个节点的引用。

​ 现在,我们分析实现的性能 这样我们就能提供给客户算法数据结构的 性能信息。这个例子中,很容易就能看出每个操作 最坏情况下只需要常数时间。每个操作没有循环,这显然是我们很想要的特性。那么空间需求呢?这和机器具体 实现有关。这是个典型Java实现,每个对象会有16字节的 额外空间,因为有内部类,所以还有8字节的额外空间 在类Node中有两个引用 一个指向字符串,另一个指向Node类 各需要8字节,每个栈节点需要40字节,如果栈大小为N 需要大约40N字节。

​ 另一种实现栈的自然的方式是使用数组来储存栈上的元素。

package Stack;

public class StackArray {
    private int top;
    private int[] arr;

    public StackArray(int size) {
        arr = new int[size];
    }

    public boolean isEmpty() {
        return top == 0;
    }

    public void push(int num) {
        arr[top++] = num;
    }

    public int pop(){
        return arr[--top];
    }
}

使用数组 我们将栈中N个元素保存在数组中,索引为N的 数组位置对应栈顶的位置,即下一个元素加入的地方。好,要入栈 我们只需要将心元素加入s[N],要出栈则移除s[N-1]处的元素 并将N减1。那么能看到使用数组一个根本性的缺点 必须事先声明数组的大小。将元素入栈,我们将元素放在N索引的位置 并将N增加1。这是现在很多编程语言表示使用索引N 并增加1的简洁表示。将元素出栈,我们将索引N减1并用它 返回数组中的元素。每个操作都只需要一行代码。有一个问题 客户端是否能向数据结构中插入空元素。这种情况中,我们 确实允许客户端插入空元素,但在Java中我们需要操心一个问题 叫做对象游离(loitering),即在栈的数组 实现中有对象的引用,而我们并没有真正使用它 所以当减小N时,在数组中仍然有我们已经出栈 的对象的指针。尽管我们知道我们不再使用它了,但是Java系统 不知道。所以为了避免这个问题,最有效地使用内存 最好将去除的元素对应的项设为null,这样就不会剩下 旧元素的引用。因为不存在引用了接下来垃圾回收器会收回那些内存。这个问题比较细节,但是很重要 我们必须在实现中要确保充分利用内存。

​ 那么,栈的基本数组实现具有需要 客户端事先提供栈的最大容量的缺点。我们没有 严格按照API的要求。API就是要求我们能够建立一个栈 并且能够增长或者缩小到任意大小。首先会想到的也许是当客户端入栈新元素时 将栈的大小增加1,当出栈时 将栈的大小减小1。代码实现不难,但是不值得这么做,因为这么做 开销太大了。因为你必须创建大小大一个元素的 新的数组,然后把所有的元素复制到新的数组中。所以如果栈大小为N-1 插入N个元素需要的时间和N成正比 如果栈大小为N-2,需要正比于N-1的时间。所以前N个元素需要的时间就是对 前N个整数求和,我们知道这大约是N^2 / 2。往栈里插入N个元素 需要平方时间,我们已经看到过很多次,这样的性能对于 巨大的问题是不可接受的。

​ 那么,调整大小是个挑战 但要通过某种方式确保它并不会经常发生。处理这个问题 有个著名的方法叫反复倍增,当数组填满时 建立一个大小翻倍的新数组,然后将所有元素复制过去,我们就不会 那么频繁地创建新数组。这就是那个方法的实现。从大小为1的 数组开始。如果我们检测到N即栈中元素的个数与数组 长度相等,则栈满了,那么我们就在插入元素之前 将数组长度调整为两倍。我们如何调整为更大的数组呢? 我们创建具有目标容量的新的数组,然后把 当前栈复制到新数组的前一半,然后返回 重新设置实例变量,我们的栈就有了更大的数组 这样做导致如果你向一个具有这种 数组表示的栈中插入N个元素,时间复杂度 与N而不是N^2成正比。因为你只有在数组大小翻倍时 才创建新的数组。而当数组翻倍时,你已经往栈里插入了 那么多的元素。所以平均下来就像每次插入只需要一个操作 所以,如果我们计算一下开销,插入前N个元素 你不需要花费从1到N之和的时间,而是 对二的幂从1到N求和 这样,总的开销大约是3N。所以,push 时先要访问数组一次,对于复制 要访问两次。所以,要插入元素,大约需要访问数组三次 这个图标是观察时间开销的另一种方式,表示出了实现 入栈操作需要访问数组的次数。每次遇到2的幂,需要进行那么多次 数组访问,但是从宏观上来看你是将那些元素放在栈上花去了那么多时间 这叫做平摊分析。考虑开销时 将总的开销平均给所有的操作。

​ 这是一个很好而且 有用的平摊分析的例子,我们分析出了栈实现的效率 出栈呢?我们需要考虑如何缩小数组 我们也许这么考虑,当数组满了的时候将容量翻倍,那么当它 只有一半满的时候,将容量缩减一半。我们不想这样做,这个办法并不如我们所愿解决问题。因为有一种现象叫做 抖动(thrashing)。如果客户端刚好反复交替入栈出栈入栈出栈 当数组满了就会反复翻倍减半翻倍减半,并且 每个操作都会新建数组,都要花掉正比与N的时间 这样就会导致平方时间,我们不想这样 有效的解决方案是直到数组变为1/4满的时候才将容量减半 实现起来也很容易,我们只要测试数组是否为 1/4满,如果是,则调整大小使其为半满。

​ 这是两种 API相同的不同的实现,客户端可以互换使用。哪个更好呢? 很多情形中,我们会有同一API的多种实现 你需要根据客户端的性质选择 合适的实现。对于链表,每个操作最坏情况下 需要常数时间,这是有保障的。但是为了处理链接 我们需要一些额外的时间和空间。所以链表实现会慢一些 可调大小的数组实现有很好的分摊时间,所以整个过程 总的平均效率不错,浪费更少的空间,对于每个操作 也许有更快的实现,所以对于一些客户端,也许会有区别 以下这样的情形你不会想用可调大小数组实现 你有一架飞机进场等待降落 你不想系统突然间不能高效运转 或者互联网上的一个路由器,数据包以很高的速度涌进来 你不想因为某个操作突然变得很慢而丢失 一些数据。客户端就可以权衡,如果想要 获得保证每个操作能够很快完成,就使用 链表实现,如果不需要,只是关心总的时间 可能就是用可调大小数组实现,因为总的 时间会小得多,单个操作非常快。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【今日问题】变量未初始化引起的崩溃

昨天写的今日问题,有小伙伴给我反馈,觉得挺有用,小编今天继续给小伙伴们总结遇到的常见问题 一、初学者经常由于没有养成良好的编程习惯,未初始化变量会引起那些问题 ...

29660
来自专栏玄魂工作室

如何学python 第八课 流程控制-For,While,循环语句,函数

循环语句 也许你会问,什么是‘循环’?在脚本程序里,循环就是‘在一定情况下一次又一次的执行某些代码’。举个例子来说,假设你很饿,桌上有好多好多个馒头,当你依旧饿...

35090
来自专栏程序你好

C# 7.3新特性一览

10430
来自专栏菜鸟计划

angularjs filter详解

过滤器(filter)正如其名,作用就是接收一个输入,通过某个规则进行处理,然后返回处理后的结果。 主要用在数据的格式化上,例如获取一个数组中的子集,对数组中的...

38280
来自专栏Python中文社区

Python生成器的使用技巧详解

之前我们介绍了列表解析式,他的优点很多,比如运行速度快、编写简单,但是有一点我们不要忘了,他是一次性生成整个列表。如果整个列表非常大,这对内存也同样会造成很大压...

14230
来自专栏北京马哥教育

对Python老司机99%有帮助的简明语法总结乱编

本文由马哥教育Python实战开发班6期学员推荐,转载自互联网,作者为赖笔小新,感谢作者的辛苦付出和贡献。 最近发现进入python群的朋友都在你是如何自学py...

31670
来自专栏架构之路

Java 中冷门的 synthetic 关键字原理解读

看JAVA的反射时,看到有个synthetic ,还有一个方法isSynthetic() 很好奇,就了解了一下: 1.定义 Any constructs int...

35950
来自专栏张善友的专栏

C# 4.0 Optional Parameters 和Named Parameters

Optional Parameters 是C# 4.0的特色之一,可减少重载函数的数量,却可达到相同的效果,加快开发效率。在使用上就跟C++一样,只需用等号为函...

21270
来自专栏JMCui

读书笔记 之《Thinking in Java》(对象、集合、异常)

一、前言:     本来想看完书再整理下自己的笔记的,可是书才看了一半发现笔记有点多,有点乱,就先整理一份吧,顺便复习下前面的知识,之后的再补上。     真的...

37980
来自专栏待你如初见

Day01

不推荐使用强制的类型转换,它容易丢失数据,除非不得已,并且你确定不会出现数据丢失才可以使用。

15850

扫码关注云+社区

领取腾讯云代金券