链表应用--基于链表实现栈

作者: wfaceboss | 来源:发表于2019-04-02 17:42 被阅读8次

    在上几小节中我们实现了基本的链表结构,并在上一节的底部给出了有关链表的源码,此处在贴一次吧,猛戳
    在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加、删除、查找操作,时间复杂度均为O(1),基于链表的这几个优势,我们在此基础上实现栈。

    image.png
    前言,在写本小节之前,我们已经实现了一个基于静态数组的栈,转到查看。此处我们实现基于链表的栈。

    1.链表类拷贝到Stack 包下:

    在实现基于静态数组的栈的时候,我们已经新建了一个package,此时我们将已经实现的链表类拷贝到该package下,目录结构为:

    image.png

    2.实现栈

    新建一个LinkedListStack类,实现Stack接口,相关代码如下:
    Stack接口:

    package Stack;
    
    public interface Stack<E> {
    
        //栈中元素个数
        int getSize();
    
        //栈中元素个数是否为空
        boolean isEmpty();
    
        //进栈
        void push(E e);
    
        //出栈
        E pop();
    
        //查看栈顶元素
        E peek();
    }
    

    LinkedListStack类:

    package Stack;
    
    public class LinkedListStack<E> implements Stack<E> {
        private LinkedList<E> list;
    
        public LinkedListStack() {
            list = new LinkedList<E>();
        }
    
        //栈中元素个数
        @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();
        }
    
    }
    

    3.添加测试代码

    为了测试的简单,我们在已经实现了Stack接口的LinkedListStack类中建立以main()方法,main中代码如下:

    //测试
        public static void main(String[] args) {
            LinkedListStack<Integer> stack = new LinkedListStack<Integer>();
            for (int i = 0; i < 5; i++) {
                stack.push(i);
                System.out.println(stack);
            }
            System.out.println("出栈一个元素:");
            stack.pop();
            System.out.println(stack);
        }
    

    结果为:


    image.png
    image.png

    关于本小节,若您觉得还行、还过得去,记得给个推荐哦~,谢谢!!

    本节源码 https://github.com/FelixBin/dataStructure/blob/master/src/Stack/LinkedListStack.java

    相关文章

      网友评论

        本文标题:链表应用--基于链表实现栈

        本文链接:https://www.haomeiwen.com/subject/cntnbqtx.html