• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(3.6)使用链表实现栈

极客笔记 Geekerstar 11个月前 (05-12) 371次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

使用链表实现栈

前面已经完成了整个链表的底层实现,也对链表的时间复杂度进行了分析。

如果我们只对链表的头进行增和删的话,时间复杂度是O(1)的。

如果我们只查链表头,时间复杂度也是O(1)的。

满足这些条件,相应的数据结构是什么呢?

大家肯定已经想到了,那就是“栈”,栈是后入先出的,只对栈的一端也就是栈顶进行操作。

无论是添加元素、删除元素还是查看元素都在栈顶进行,所以对应我们的链表,就可以把链表头当做栈顶,来实现栈这样一个数据结构。

我们将使用上一章设计的接口,实现LinkedListStack,也就是用链表来实现的栈。

代码演示

新创建一个链表栈LinkedListStack,代码如下:

public class LinkedListStack<E> implements Stack<E> {

    private LinkedList<E> list;

    public LinkedListStack(){
        list = new LinkedList<>();
    }

    @Override
    public int getSize(){
        return list.getSize();
    }

    @Override
    public boolean isEmpty(){
        return list.isEmpty();
    }

    @Override
    public void push(E e){
        list.addFirst(e);
    }

    @Override
    public E pop(){
        return list.removeFirst();
    }

    @Override
    public E peek(){
        return list.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }

    public static void main(String[] args) {

        LinkedListStack<Integer> stack = new LinkedListStack<>();

        for(int i = 0 ; i < 5 ; i ++){
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

运行结果如下:

仔细观察并分析一下结果,链表的左侧是栈顶,初始的时候是0,依次把1,2,3,4压入栈,最后有一个出栈操作,把栈顶的4给拿出来。

比较一下链表栈和数组栈

来编写一个测试函数来比较链表栈和数组栈

import java.util.Random;

public class Main {

    // 测试使用stack运行opCount个push和pop操作所需要的时间,单位:秒
    private static double testStack(Stack<Integer> stack, int opCount){

        long startTime = System.nanoTime();

        Random random = new Random();
        for(int i = 0 ; i < opCount ; i ++)
            stack.push(random.nextInt(Integer.MAX_VALUE));
        for(int i = 0 ; i < opCount ; i ++)
            stack.pop();

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 100000;

        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        double time1 = testStack(arrayStack, opCount);
        System.out.println("ArrayStack, time: " + time1 + " s");

        LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
        double time2 = testStack(linkedListStack, opCount);
        System.out.println("LinkedListStack, time: " + time2 + " s");

        // 其实这个时间比较很复杂,因为LinkedListStack中包含更多的new操作
    }
}

运行一下这个程序,结果如下:

对于十万个数据而言,在我的机子上得到的结果是这样的。

对于数组栈,结果是0.0266S,对于链表栈,结果是0.0128S,链表栈比数组栈要快一些。

原因是对于数组栈,时不时的要重新分配一下整个的静态数组,然后将原来数组中的元素复制的新的数组中,对于链表栈并不存在这种情况。

但是不管怎样,这二者在我们这个实现中是同一复杂度的,在不同的情况下,谁比谁多或者谁比谁少一点都是正常的,他们之间没有复杂度的巨大差异。

在上一章我们实现的循环队列和数组队列之间的差异是巨大的,这样巨大的差异是我们算法复杂度差异造成的。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(3.6)使用链表实现栈
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00