数据结构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 条评论
登录 后参与评论

相关文章

  • 数据结构Queue

    ​ 栈和队列其实是相同的,只是名字不一样 入栈换成了入队(enqueue),出栈换成了出队(dequeue)。语义 是不同的。入队操作向队尾添加元素,而出...

    lwen
  • Java集合框架Collections

    1.基本介绍: 集合就是存放对象的,他比数组好的一点就是他一开始不清楚自己长度 容器一般是分为很多种的,很多的容器在一起然后进过断的抽象和抽取就成了一个体系,...

    lwen
  • 八大排序算法

    ​ 八大排序算法是面试经常考到的,尤其是快排,希尔排序和归并也是经常会让写代码的题目,其实只要用一句话说明了他们的原理我们写起代码就没那么困难。 冒泡排序...

    lwen
  • 怀英漫谈9 - JS 数组

    所谓的数组,就是一些数据的集合,JS中没有集合的概念,所以集合也是数组的一种。如果你Java用的多,那么这个概念就有点儿难以理解,毕竟从Java的文意来说,集合...

    用户1335799
  • 【30秒一个知识点】Array(二)

    使用 Array.from()创建一个新的数组,该数组与将要生成的块的数量相匹配。 使用 Array.prototype.slice() 将新数组的每个元素映射...

    ConardLi
  • 编程小白 | 每日一练(33)

    这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

    C语言入门到精通
  • [Go] Golang练习项目-GO语言实现插入排序

    将数组分成已排序和待排序两部分,将一个元素从待排序插入到有序数组的适当位置,直到所有待排序都插入完成

    陶士涵
  • [jQuery笔记] jQuery语法

    jquert语法通常是选取html元素,并对所则的元素执行某些操作(actions)

    行 者
  • js 数组方法大集合,各方法是否改变原有的数组详解

    不会改变原来数组的有: concat()---连接两个或更多的数组,并返回结果。

    IT人一直在路上
  • JS数组操作

    1)delete方法:delete arr[1] 这种方式数组长度不变,此时arr[1]变为undefined了,但是也有好处原来数组的索引也保持不变,此时要遍...

    似水的流年

扫码关注云+社区

领取腾讯云代金券