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

在上几小节中我们实现了基本的链表结构，并在上一节的底部给出了有关链表的源码，此处在贴一次吧，猛戳
在开始栈的实现之前，我们再来看看关于链表的只在头部进行的添加、删除、查找操作，时间复杂度均为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

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

本节源码 FelixBin/dataStructure/blob/master/src/Stack/LinkedListStack.java