LinkedList Stack 链表栈

栈的实现

栈的实现有多种方式，一种是通过动态数组, 另一种是通过链表。

为了增强代码的复用性和解耦，我们不从头实现一个栈。而是定义一个栈的接口, 动态数组或者链表，去实现这个接口即可。而事实上，通过我们上前面学的 LinkedList 链表来实现一个栈是非常简单的。

public interface Stack<E>{

    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();

}

push()方法 将一个元素入栈。peek() 方法返回栈顶的元素，但是不取出。pop()方法取出栈顶元素并返回。其他两个方法与 LinkedList 相同, 这里就不做解释了。

随后我们定义一个 LinkedListStack 类去实现 Stack 接口即可。

public class LinkedListStack<T> implements Stack<T> {
    private LinkedList<T> list;

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

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

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

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

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

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

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


}

测试一下

最后我们在 main 方法内进行测试。我们依次向栈内push 数字0到5， 随后打印输出，再pop两次，再次输出.

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();
    stack.pop();
    System.out.println(stack);
}

输出结果:

Stack: top 0->Null
Stack: top 1->0->Null
Stack: top 2->1->0->Null
Stack: top 3->2->1->0->Null
Stack: top 4->3->2->1->0->Null
Stack: top 2->1->0->Null