数据结构Java版（5）——链栈和链队列的实现

? ? ? ? ? 之前我们对链表进行了讲解，这次我们来用链表的方式来实现栈和队列两个接口，来加深我们对链表的理解。

一、链栈

? ? ? ? 栈的接口与顺序栈的接口相同，这里我们主要展示如何用我们自己写的链表来实现这个接口，代码展示如下：

接口实现类

public class LinkedStack<T> implements Stack_i<T>{
    private LinkedList<T> stack;

    public LinkedStack() {
        this.stack = new LinkedList<>();
    }

    @Override
    public boolean push(T e) {
        return stack.addFirst(e);
    }

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

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

    @Override
    public int getLength() {
        return stack.getLength();
    }

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

对我们的链栈进行测试

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class testMyStack {
    public static void test(Stack_i<Integer> stack, List<Integer> list){
        Random random = new Random();
        for(int i = 0;i < 10;i++){
            stack.push(random.nextInt(1000));
            System.out.println(stack.peek()+"——现在还有"+stack.getLength()+"个元素");
        }
        Integer temp;
        while ((temp = stack.pop())!=null){
            list.add(temp);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList();
        Stack_i<Integer> stack = new LinkedStack<>();
        test(stack,list);
        for (Integer i:list) {
            System.out.println(i);
        }
    }
}

输出结果：

二、链队列

? ? ? ? ?这里接口也是与顺序队列的相同，直接进行代码展示：

接口实现类

public class LinkedQueue<T> implements Queue_i<T>{
    private LinkedList<T> queue;

    public LinkedQueue() {
        this.queue = new LinkedList<T>();
    }

    @Override
    public boolean offer(T e) {
        return queue.addFirst(e);
    }

    @Override
    public T poll() {
        return queue.removeLast();
    }

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

    @Override
    public int getLength() {
        return queue.getLength();
    }

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

    @Override
    public T peekLast() {
        return queue.getLast();
    }
}

对我们的链队列进行测试

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class testMyQueue {

    public static void test(Queue_i<Integer> queue){
        List<Integer> list = new ArrayList();
        Random random = new Random();
        for(int i = 0;i < 16;i++){
            queue.offer(random.nextInt(100));
            System.out.println(queue.peek()+"——现在还有"+queue.getLength()+"个元素");
        }
        Integer temp;
        for(int i = 0;i < 2;i++){
            System.out.println(queue.poll());
        }
        for(int i = 0;i < 5;i++){
            queue.offer(random.nextInt(100));
            System.out.println(queue.peek()+"——现在还有"+queue.getLength()+"个元素");
        }
        while ((temp = queue.poll())!=null){
            list.add(temp);
        }
        for (Integer i:list) {
            System.out.println(i);
        }

    }

    public static void main(String[] args) {
        Queue_i<Integer> queue = new LinkedQueue<>();
        test(queue);

    }
}

输出结果：

三、总结

? ? ? ? ? 在日常使用中，链队列用的多一点，且在链队列之上，又有了双端队列等应用，说明链表在Java中十分重要。