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

使用链表实现栈

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

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

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

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

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

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

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

代码演示

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

public class LinkedListStack implements Stack {

    private LinkedList 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 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 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 arrayStack = new ArrayStack<>();
        double time1 = testStack(arrayStack, opCount);
        System.out.println("ArrayStack, time: " + time1 + " s");

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

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

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

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

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

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

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

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

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(3.6)使用链表实现栈

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多