最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(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)使用链表实现栈

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 176会员总数(位)
    • 3737资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 542稳定运行(天)

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

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级